2nd Shortest Path

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define all(x) x.begin(), x.end()
#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define fd(i,a,b) for(int i = (a); i >= (b); i--)
#define mp make_pair
#define faster_io() ios_base::sync_with_stdio(false)
#define pb push_back
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define vii vector< pair<int,int> >

const int INF = 1000000007;
const ll INFLL = 100000000000000000ll;
const ll MOD = 1000000007;

// ----------------------------------------------------------------------------------------------------------

int D[5005][2], T, N, M;
vii E[5005];

int main()
{
    cin >> T;

    f(tt,1,T)
    {
        cin >> N >> M;
        f(i,1,N) E[i].clear(), D[i][0] = D[i][1] = INF;

        f(i,1,M)
        {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            E[a].pb(mp(b,c)), E[b].pb(mp(a,c));
        }

        priority_queue<pair<int, pii >,vector<pair<int, pii > >,greater<pair<int, pii > > > q;
        D[1][0] = 0;
        q.push(mp(0,mp(1,0)));

        while(!q.empty())
        {
            pair<int,pii> p = q.top();
            q.pop();

            int n = p.second.first, j = p.second.second, d = p.first;
            if(d > D[n][j]) continue;

            for(int i = 0; i < SZ(E[n]); i++)
            {
                pii pr = E[n][i];
                int nd = d + pr.second;
                int v = pr.first;

                if(nd < D[v][0])
                {
                    D[v][1] = D[v][0];
                    q.push(mp(D[v][1],mp(v,1)));
                    D[v][0] = nd;
                    q.push(mp(nd,mp(v,0)));
                }
                else if(nd > D[v][0] && nd < D[v][1])
                {
                    D[v][1] = nd;
                    q.push(mp(nd,mp(v,1)));
                }
            }
        }

        cout << "Case " << tt << ": " << D[N][1] << "\n";
    }
}