LOJ_1002 - Country Roads

//============================================================================
// code written by unlucky_13
//============================================================================

#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<list>
#include<sstream>
#include<fstream>
#define INF 1<<29

using namespace std;

int n,m ;


struct data
{  int city,cost ;
bool taken ;
    bool operator < ( const data& p ) const {
        return cost > p.cost;
    }
};

vector<data>edg[500] ;
int dis[500+10] ;



void dijkstra(int source){


    for(int i=0;i<n;i++) dis[i] = INF ;
    dis[source] = 0 ;
    priority_queue<data>pq ;
    data p,q ;
    p.city = source ;
    p.cost = 0 ;
    pq.push(p) ;
    while(!pq.empty()){

        p = pq.top() ; pq.pop() ;


        for(int i=0;i<edg[p.city].size();i++) {

            q = edg[p.city][i] ;

            if(dis[q.city]>max(dis[p.city],q.cost)){
                pq.push(edg[p.city][i]) ;
                dis[q.city] = max(dis[p.city],q.cost) ;
            }
        }

    }
}



int main() {
    //freopen("d:\\in.txt","r",stdin) ;

    int t,u,v,cost,caseno=0,testcase ;
    data G ;
    scanf("%d",&testcase) ;
    while(testcase--){
        scanf("%d %d",&n,&m) ;
        for(int i=0;i<=500;i++) edg[i].clear() ;
        for(int i=0;i<m;i++){
        scanf("%d %d %d",&u,&v,&cost) ;
        G.city = u ; G.cost = cost ; G.taken = false ;
        edg[v].push_back(G) ;
        G.city = v ;
        edg[u].push_back(G) ;
        }
        scanf("%d",&t) ;
        dijkstra(t) ;
        printf("Case %d:\n",++caseno) ;
        for(int i=0;i<n;i++){
            if(dis[i]==INF) cout<<"Impossible"<<endl ;
            else cout<<dis[i]<<endl ;
        }
    }

    return 0;
}