UVA 10986 / Dijkstra Basic

/***
 created: 2022-06-20-16.28.23
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

vector<pair<ll,ll>>g[200005];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    test
    {
        ll n,m,i,j,k,l,s,d;

        cin>>n>>m>>s>>d;


        ll cost[n+5];

        fill(cost,cost+n+2,1e17);


        while(m--)
        {
            ll a,b,c;

            cin>>a>>b>>c;

            g[a].push_back({b,c});
            g[b].push_back({a,c});
        }

        cost[s]=0;

        priority_queue<ll>q;

        q.push(s);

        while(q.empty()==false)
        {
            ll u=q.top();
            q.pop();

            for(auto i:g[u])
            {
                if(cost[i.first]> cost[u]+i.second)
                {
                    cost[i.first]=cost[u]+i.second;
                    q.push(i.first);
                }
            }
        }

        cout<<"Case #"<<cs<<": ";

        if(cost[d]==(1e17)) cout<<"unreachable"<<nl;
        else cout<<cost[d]<<nl;

        for(i=0;i<n;i++) g[i].clear();

    }


    get_lost_idiot;
}