400908: GYM100283 B Egyptian Roads Construction

Welcome to Egypt!!! where you can wait for decades for the government to accomplish something useful!. The roads of the city are completely damaged and haven't been maintained for years. The people of the city have made several requests to pave and maintain the streets to the governor but there was no response. Lately the governor was changed and to satisfy the people of the city the governor promised to do his best to get the streets paving budget from the government. In order to request the budget an estimation for the cost must be conducted. This estimation can be done by a company but it will cost a lot of money, and moreover, the city will have to wait for the governor to request an approval from the government to get the company expenses. Taking this option will get the city into "the chicken or the egg" dilemma.

Being positive citizens; Bakkar & Hassona decided to conduct this estimation using voluntary efforts from the people of the city. They decided to make you in charge of the team responsible for the estimation as you are an expert in road construction techniques and have some background in graph theory.

The graph of the city can be described as an undirected graph consisting of M edges (representing the city's roads) and N nodes (representing the roads' intersections), where each edge connects exactly two nodes and every road has a pavement cost. To conduct the estimation; the government needs to know for every node: what is the cost of the mini-max path to every other node. A mini-max path between two nodes is a path that connects the two nodes and the maximum pavement cost on the edges of this path is minimum. The cost of a path is the maximum pavement cost among all its edges. The city roads guarantees that there is at least one path between any two nodes.

Since you are in charge of the team, you asked them to get you the pavement cost for all roads. And once you get this information you will write a program to calculate the required estimate.

To make your life easier, the governor agreed with the government that they will conduct the estimation if you provide them with a single cost for every node that represents the sum of the costs of the mini-max paths from that node to every other node. Formally, for every node i you have to provide the government with the sum of the costs of the mini-max paths between node i and every node j where 1  ≤  j  ≤  N and i  ≠  j.

Your team has got the pavement costs for all the edges ready for you. It's now your job to provide the government with the values requested.

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  50). The first line of each test case will contain two integers N (1  ≤  N  ≤  10⁵) and M (N-1  ≤  M  ≤  10⁵), the number of nodes and edges respectively. The next M lines will each contain three integers x, y and c representing an undirected road between node x and node y with pavement cost c (1  ≤  x,y  ≤  N) (0  ≤  c  ≤  1000). There will be no road connecting a node to itself and there will not be multiple roads between any two nodes.

For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1). Then for each node i (1  ≤  i  ≤  N) print on a single line the sum of the costs of the mini-max paths from node i to every other node in the city.

2
5 7
1 2 2
1 4 5
2 3 14
2 4 5
2 5 4
3 5 34
4 5 58
7 11
1 2 40
1 3 8
1 4 11
2 3 29
2 6 17
3 4 3
3 6 31
4 5 46
5 6 40
5 7 15
6 7 53

Case 1:
25
25
56
29
27
Case 2:
154
184
149
149
215
184
215

Warning: large Input/Output data, be careful with certain languages.