Not The Best Lightoj

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#include<string.h>
using namespace std;
#define pb          push_back
#define all(v)      v.begin(),v.end()
#define ya          cout<<"YES"<<endl;
#define no          cout<<"NO"<<endl;
#define ff          first
#define sc          second
#define inf         999999999
#define pi          3.14159265359
#define printv(v)   for(auto x:v)cout<<x<<' ';cout<<endl;
#define takev(v)    for(auto &x:v)cin>>x;
inline  int         random(int a=1,int b=10)
{
    return a+rand()%(b-a+1);
}
typedef long long ll;
inline ll           lcm(ll a,ll b)
{
    return (a*b)/__gcd(a,b);
}
//#define see(x)  cout<<endl<<#x<<" : "<<(x)<<endl;
#define see(args...) \
{ \
    string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
    stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);\
}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cout<< *it << " = " << a <<",\n"[++it==istream_iterator<string>()];
    err(it, args...);
}
#define scc(n) scanf("%d",&n);
#define sccc(n) scanf("%lld",&n);

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int N=5009,mod=998244353;

int d[N][N];
int n,r;
vector< pair<int,int> >G[N];


void shortest_length(int source)
{
    d[source][source] = 0;
    priority_queue< pii > q;
    q.push({0,source});

    while(!q.empty())
    {
        int a = q.top().sc;

        q.pop();

        for(auto [b,length]:G[a])
        {
            if(d[source][a] + length < d[source][b])
            {
                d[source][b] = d[source][a] + length;
                q.push({-d[source][b],b});
            }
        }
    }
}
int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(NULL);


    int _,t=0;

    scc(_);

    while(++t <= _)
    {
        scc(n)
        scc(r)

        for(int i=1;i<=n;i++)G[i].clear();

        int ans = INT_MAX;

        for(int i=0;i<r;i++)
        {
            int x,y,c;
            scc(x)
            scc(y)
            scc(c)
            G[x].pb({y,c});
            G[y].pb({x,c});
        }

        fill(d[1],d[1]+N-1,inf);
        fill(d[n],d[n]+N-1,inf);

        shortest_length(1);
        shortest_length(n);

        int best = d[1][n];

        for(int a=1;a<=n;a++)
        {
            for(auto [b,l]:G[a])
            {
                if(d[1][a] + d[n][b] + l > best)
                    ans = min(ans,d[1][a] + d[n][b] + l);

            }
        }

        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}