Light OJ 1019 (Brush (V))

#include<bits/stdc++.h>
#define mx 1000000
#define inf 1e8
using namespace std;
typedef long long ll;
ll dist[mx];
list<pair<ll,ll> > *graph;
void dijksra(ll root)
{
    set<pair<ll,ll> >pq;
    set<pair<ll,ll> > :: iterator it;
    ll u,v,w,wt;
    list<pair<ll,ll> > :: iterator i;
    dist[root]=0;
    pq.insert(pair<ll,ll>(0,root));
    while(pq.size()!=0)
    {
        it=pq.begin();
        u=it->second;
        pq.erase(it);
        for(i=graph[u].begin();i!=graph[u].end();i++)
        {
            v=i->first;
            wt=i->second;
            if(dist[v]>dist[u]+wt)
            {
                if(dist[v]!=inf)
                {
                    pq.erase(pq.find(pair<ll,ll>(dist[v],v)));
                }
                dist[v]=dist[u]+wt;
                pq.insert(pair<int,int>(dist[v],v));

            }
        }
    }
}
void add(ll src,ll des,ll wt)
{
    pair<ll,ll>x;
    x.first=des;
    x.second=wt;
    graph[src].push_front(x);
    x.first=src;
    x.second=wt;
    graph[des].push_front(x);
    //cout<<111<<endl;
}
int main()
{
    ll i,j,k,l,m,n,test,edge,node,cs=1;
    cin>>test;
    while(test--)
    {
        cin>>node>>edge;
        for(i=0;i<mx;i++)
        {
            dist[i]=inf;
        }
        graph=new list<pair<ll,ll> > [node+1];
        for(i=0;i<edge;i++)
        {
            ll src,dest,wt;
            cin>>src>>dest>>wt;
            add(src,dest,wt);
        }
        ll start,stop;
        start=1;
        stop=node;
        dijksra(start);
        cout<<"Case "<<cs<<": ";
        if(dist[stop]!=inf)
        {
            cout<<dist[stop]<<endl;
        }
        else
        {
            cout<<"Impossible"<<endl;
        }
        cs++;
    }
    return 0;
}