
98  The 2010 ACMICPC Asia Chengdu Regional Contest  B
It is vitally important to have all the cities connected by highways in a war, but some of them are destroyed now because of the war. Furthermore, if a city is conquered, all the highways from/toward that city will be closed by the enemy, and we must repair some destroyed highways to keep other cities connected, with the minimum cost if possible. Given the map of cities which have all the destroyed and remaining highways marked, you are supposed to tell the cost to connect other cities if each city is conquered by the enemy. Input
The input contains multiple test cases. The first line is the total number of cases T (T ≤ 10).
Each case starts with a line containing 2 numbers N (0 < N ≤ 20000), and M (0 ≤ M ≤ 100000), which are the total number of cities, and the number of highways, respectively. Then M lines follow, each describes a highway by 4 integers: Note: It is guaranteed that the whole country was connected before the war and there is no duplicated high ways between any two cities. Output For each test case, output N lines of integers. The integer in the ith line indicates the cost to keep the cities connected if the ith city is conquered by the enemy. In case the cities cannot be connected after the ith city is conquered by the enemy, output "inf" instead in the corresponding place. Sample Input 3 4 5 1 2 1 1 1 3 1 1 2 3 1 0 2 4 1 1 3 4 2 0 4 5 1 2 1 1 1 3 1 1 2 3 1 0 2 4 1 1 3 4 1 0 3 2 1 2 1 1 1 3 1 1 Sample Output 1 2 0 0 1 1 0 0 inf 0 0 Author: GUAN, Yao Source: The 2010 ACMICPC Asia Chengdu Regional Contest 