light oj 1099

#include<bits/stdc++.h>

using namespace std;

#define mx 5005

vector<long long>edge[mx],cost[mx];

const long long infinity = 1000000000;

int dis[2][mx];
//bool vis[2][mx];

void dijkstra(int des)
{

    priority_queue< pair<int,pair<long long,long long> > >pq;

    pq.push(make_pair(1,make_pair(0,1)));
    dis[1][1]=0;
    while(!pq.empty())
    {
        int f=pq.top().first;
       int u=pq.top().second.second;
        pq.pop();
      //  if(vis[f][u])
           // continue;
           // vis[f][u]=true;
        long long ucost=dis[f][u];
        for(long long i=0; i<edge[u].size(); i++)
        {
            long long v=edge[u][i];
            long long vcost=cost[u][i]+ucost;
            if(dis[1][v]>vcost)
            {
                dis[2][v]=dis[1][v];
                 pq.push(make_pair(2,make_pair(-dis[2][v],v)));
                dis[1][v]=vcost;
                pq.push(make_pair(1,make_pair(-dis[1][v],v)));

            }
            else if(vcost>dis[1][v]&&vcost<dis[2][v])
            {
                dis[2][v]=vcost;
                  pq.push(make_pair(2,make_pair(-dis[2][v],v)));
                            }
        }
    }
}
int main()
{
    int n,m,u,v,c,test;
    cin>>test;
    for(long long j=1; j<=test; j++)
    {
        cin>>n>>m;
    for(int i=1; i<mx; i++)
        {

            dis[1][i]=  dis[2][i] = infinity;
         //vis[1][i]=false;
           // vis[2][i]=false;
        }
        for(long long i=0; i<m; i++)
        {
            cin>>u>>v>>c;
            edge[u].push_back(v);
            cost[u].push_back(c);
            edge[v].push_back(u);
            cost[v].push_back(c);
        }


        dijkstra(n);
        cout<<"Case "<<j<<": "<<dis[2][n]<<endl;
        for(long long k=0; k<mx; k++)
        {
            edge[k].clear();
        }
        for(long long k=0; k<mx; k++)
        {
            cost[k].clear();
        }
    }

}