(Really) Second Best Shortest Path - LOJ 1099

//{ ************[       Template       ]************
using namespace std;
//{ ************[      C headers       ]************
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cfloat>
#include <cctype>
#include <cassert>
#include <ctime>
//}
//{ ************[     C++ headers      ]************
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <complex>
//{ ************[     Test Report 1    ]************
// #include <tr1/regex>
// #include <tr1/unordered_set>
// #include <tr1/unordered_map>
//}
//}
//{ ************[        Loops         ]************
#define forab(i, a, b)          for (__typeof(b) i = (a); i <= (b); ++i)
#define rep(i, n)       forab (i, 0, (n) - 1)
#define For(i, n)       forab (i, 1, n)
#define rofba(i, a, b)          for (__typeof(b) i = (b); i >= (a); --i)
#define per(i, n)       rofba (i, 0, (n) - 1)
#define rof(i, n)       rofba (i, 1, n)
#define forstl(i, s)            for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
//}
//{ ************[   Floating points    ]************
#define EPS         DBL_EPSILON
#define abs(x)          (((x) < 0) ? - (x) : (x))
#define zero(x)         (abs (x) < EPS)
#define equal(a,b)      (zero ((a) - (b)))
#define PI          2 * acos (0.0)
//}
//{ ************[        Macros        ]************
#define mem(a, i)       memset ((a), i, sizeof ((a)))
#define clr(a)          mem ((a), 0)
#define all(a)          (a).begin (), (a).end ()
#define pb          push_back

template <class T, class U> inline T max (T &a, U &b) { return a > b ? a : b; }
template <class T, class U> inline T min (T &a, U &b) { return a < b ? a : b; }
static struct _ { ios_base :: Init Init; _ () { cin.sync_with_stdio (false); cin.tie (false); } } _;
//}
//{ ************[  Typedefs && Consts  ]************
typedef long long int64;
typedef unsigned long long int64u;

const int MAX_N = int (5e3) + 7;
const int MOD   = int (1e9) + 7;
//}
//}

int best, sBest, s [MAX_N], d [MAX_N];
vector <pair <int, int> > adjList [MAX_N];

priority_queue <int, vector <int>, greater <int> > Q;

void dijkstra (int source, int cost [MAX_N]) {
    fill (cost, cost + MAX_N, 1 << 22);
    cost [source] = 0;
    Q.push (source);

    while (!Q.empty ()) {
        int u = Q.top ();
        Q.pop ();
        forstl (i, adjList [u]) {
            int v = i -> first;
            int w = i -> second;
            if (cost [v] > cost [u] + w) cost [v] = cost [u] + w, Q.push (v);
        }
    }
}

void cherry (int val) {
    if (val < best) {
        sBest = best;
        best  = val;
    } else if (val < sBest && val > best) sBest = val;
}

int main () {
#ifdef Local
    freopen ("input.txt", "r", stdin);
    // freopen ("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;

    For (cs, t) {
        int n, r;
        cin >> n >> r;

        rep (i, MAX_N) adjList [i].clear ();
        rep (i, r) {
            int u, v, w;
            cin >> u >> v >> w;
            adjList [u - 1].pb (make_pair (v - 1, w));
            adjList [v - 1].pb (make_pair (u - 1, w));
        }

        dijkstra (0, s);
        dijkstra (n - 1, d);

        best = sBest = 1 << 22;
        rep (i, n) {
            cherry (s [i] + d [i]);
            forstl (u, adjList [i]) cherry (s [i] + d [u -> first] + u -> second);
        }

        cout << "Case " << cs << ": " << sBest << endl;
    }
    return 0;
}