I 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.
For example, in the above picture, if we want to go from 0 to 4, then we can choose
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’.

Note

Dataset is huge, user faster I/O methods.

题意：

给你一张无向图，给出一个起点，问从这个起点出发，到达每个点的最小路径是多少，最小路径的定义是指从A到B所经过的所有边中边权最大值，也就是说，你从A到B无论绕多远，只要你经过的路径上边权最大值最小即为最优。
输入时，先给你n和m，然后m行，表示从u到v有一条权值为c的双向边，最后一行表示起点。
输出时，首先输出是第几组测试数据，然后接下来n行，每行代表从初始点到其他点的最小路径是多少，如果不能到达，则输出Impossible。

题解：

首先我们考虑一条链的情况，我们从起点到其他点时，一定会经过这个点到起点之间所有的边，那么前面的最大值就会是起点到这个点答案（如果这个点的边比最大值小），所以我们只要局部最优即可，然后关于如何实现图联通，还要连上的边权值尽可能的小，那么自然而然的想到了最小生成树。
我们首先通过最小生成树建好图然后遍历一下整张图即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int fst[2333], nxt[33333], dis[505];
int fa[600], tot = 0;
bool used[2333];
struct qer
{
    int from, to, cost;
}es[23333], es2[23333];
queue <int> q;
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool cmp(qer a, qer b)
{
    return a.cost < b.cost;
}
void build(int f, int t, int d)
{
    es[++tot] = (qer){f, t, d};
    nxt[tot] = fst[f];
    fst[f] = tot;
}
void bfs(int x)
{
    while (!q.empty())
        q.pop();
    memset (used, 0, sizeof(used));
    q.push(x);
    used[x] = 1;
    dis[x] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = fst[u]; i; i = nxt[i])
        {
            int v = es[i].to;
            if (!used[v])
            {
                if (es[i].cost > dis[u])
                    dis[v] = es[i].cost;
                else
                    dis[v] = dis[u];
                q.push(v);
                used[v] = 1;
            }
        }
    }
}
int main()
{
    int T;
    cin >> T;
    for (int sss = 1; sss <= T; sss++)
    {
        int n, m, sum = 0, t;
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= n; i++)
            fa[i] = i, dis[i] = -1;
        memset (fst, 0, sizeof(fst));
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &es[i].from, &es[i].to, &es[i].cost);
        cin >> t;
        sort (es + 1, es + m + 1, cmp);
        for (int i = 1; i <= m; i++)
        {
            int x = find(es[i].from), y = find(es[i].to);
            if (x != y)
            {
                fa[x] = y;
                es2[++sum] = es[i];
            }
        }
        for (int i = 1; i <= sum; i++)
        {
            build (es2[i].from, es2[i].to, es2[i].cost);
            build (es2[i].to, es2[i].from, es2[i].cost);
        }
        bfs(t);
        printf("Case %d:\n", sss);
        for (int i = 0; i < n; i++)
        {
            if (dis[i] == -1)
                puts("Impossible");
            else
                printf("%d\n", dis[i]);
        }
    }
    return 0;
}