lightoj1002

maksyuki 发表于 oj 分类,标签:
0

1002 - Country Roads

For example, in the above picture, if we want to go from 0 to 4, then we can chooseI am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of my city t where I belong. Now from each city you have to find the minimum cost to go to my city. The cost is defined by the cost of the maximum road you have used to go to my city.

1)      0 - 1 - 4 which costs 8, as 8 (1 - 4) is the maximum road we used

2)      0 - 2 - 4 which costs 9, as 9 (0 - 2) is the maximum road we used

3)      0 - 3 - 4 which costs 7, as 7 (3 - 4) is the maximum road we used

So, our result is 7, as we can use 0 - 3 - 4.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a blank line and two integers n (1 ≤ n ≤ 500) and m (0 ≤ m ≤ 16000). The next m lines, each will contain three integers u, v, w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 20000)indicating that there is a road between u and v with cost w. Then there will be a single integer t (0 ≤ t < n). There can be multiple roads between two cities.

Output

For each case, print the case number first. Then for all the cities (from 0 to n-1) you have to print the cost. If there is no such path, print 'Impossible'.

Sample Input

Output for Sample Input

25 60 1 5

0 1 4

2 1 3

3 0 7

3 4 6

3 1 8

1

 

5 4

0 1 5

0 1 4

2 1 3

3 4 7

1

Case 1:403

7

7

Case 2:

4

0

3

Impossible

Impossible

Note

Dataset is huge, user faster I/O methods.

 

题目类型:最大容量路(bellman-ford)

算法分析:使用边表存储边的信息,然后使用bellman-ford迭代n – 1次计算dis数组的值,dis[i]表示节点i到目标节点的最大容量值,递推公式为

dis[edge[j].u] = min (dis[edge[j].u], max (edge[j].w, dis[edge[j].v]));注意使用Floyd会TLE