Lightoj 1019-Brush (V)

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define highest_int 2147483647
#define INF 2000000

struct edge
{
    int u ,w ;
    bool operator < (const edge & p) const
    {
        return w>p.w ;
    }
};

vector<int> G[10001] ;
vector<int> cost[1001];
int d[10001] ;

void res (int n)
{
    for(int i=1 ; i<=n ; i++)
    {
        G[i].clear() ;
        cost[i].clear() ;
        d[i] = INF ;
    }
}

int dijkstra(int n)
{
    priority_queue<edge> q ;
    edge e ;
    e.u =1 ;
    e.w =0 ;
    d[1] =0 ;
    q.push(e) ;

    while(!q.empty())
    {
        edge top = q.top() ;
        q.pop() ;
        int u = top.u ;
        if(u==n)
            return d[n] ;

        for(int i=0 ; i<G[u].size() ; i++)
        {
            int v = G[u][i] ;
            int dis = cost[u][i] ;
            if(d[u] + dis < d[v])
            {
                d[v] = dis + d[u] ;
                e.u = v ;
                e.w = d[v] ;
                q.push(e) ;
            }
        }
    }
    return -1 ;
}


int main()
{
    int test ;
    cin>>test ;
    int cnt =1 ;

    while(test--)
    {
        int n ,m ;
        cin>>n>>m ;

        res(n) ;

        for(int i=1 ; i<=m ; i++)
        {
            int u,v,w ;
            cin>>u>>v>>w ;
            cost[u].pb(w) ;
            cost[v].pb(w) ;
            G[u].pb(v) ;
            G[v].pb(u) ;
        }
        int x = dijkstra(n) ;
        if(x==-1)
            pf("Case %d: Impossible\n",cnt++) ;
        else
            pf("Case %d: %d\n",cnt++,x) ;

    }
    return 0;
}