Is There A Second Way Left?

#include<bits/stdc++.h>
#include<string.h>

using namespace std;

#define pb          push_back
#define ff          first
#define sc          second

typedef long long ll;

#define scc(n) scanf("%d",&n);
#define sccc(n) scanf("%lld",&n);

const int N=300,mod=998244353;

int nodes,edges;
bool edges_on_mst[N];
bool take_me[N];

vector< pair<int, pair<int,int> > > all_edges;

int second_mst()
{
    bool taken[N];
    memset(taken , 0, sizeof taken);

    vector< pair<int,int> > adj[N];

    for(int i=0;i<edges;i++)
    {
        if(!take_me[i])
        {
            int c,s,e;

            c = all_edges[i].ff;
            s = all_edges[i].sc.ff;
            e = all_edges[i].sc.sc;

            adj[s].pb({e,c});
            adj[e].pb({s,c});
        }
    }

    priority_queue< pair<int,int> >q;
    int ans=0;

    taken[1]=1;
    for(auto [node,weight]:adj[1])
    {
        if(!taken[node])
            q.push({-weight,node});
    }

    while(!q.empty())
    {
        int cost = -q.top().ff;
        int next = q.top().sc;

        q.pop();

        if(!taken[next])
        ans += cost;

        taken[next]=1;
        for(auto [node,cost]:adj[next])
        {
            if(!taken[node])
                q.push({-cost,node});
        }
    }

    for(int i=1;i<=nodes;i++) if(taken[i]==0)return INT_MAX;

    return ans;
}


int mst()
{
    bool taken[N];
    memset(taken , 0, sizeof taken);

    vector< pair<int , pair<int,int> > > adj[N]; /// index of the edge , next , cost

    for(int i=0;i<edges;i++)
    {
        int c,s,e;

        c = all_edges[i].ff;
        s = all_edges[i].sc.ff;
        e = all_edges[i].sc.sc;

        adj[s].pb({i,{e,c}});
        adj[e].pb({i,{s,c}});
    }

    priority_queue< pair< pair<int,int> , int > >q; /// cost , next , index of the edge

    int ans=0;

    taken[1]=1;
    for(auto [i,k]:adj[1])
    {
        if(!taken[k.ff])
            q.push( { { -k.sc, k.ff}, i} ); /// k.ff = cost , k.sc = next node;
    }

    while(!q.empty())
    {
        int cost = -q.top().ff.ff;
        int next = q.top().ff.sc;
        int edge_number = q.top().sc;

        q.pop();

        if(!taken[next])
        {
            edges_on_mst[edge_number] = 1;
            ans += cost;
        }

        taken[next]=1;
        for(auto [i,k]:adj[next])
        {
            if(!taken[k.ff])
                q.push( { { -k.sc, k.ff}, i} ); /// k.ff = cost , k.sc = next node;
        }
    }

    for(int i = 1;i<=nodes; i++) if(taken[i]==0)return -1;

    return ans;
}

int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(NULL);

    int _,t=1;
    scc(_);
    while(_--)
    {
        memset(edges_on_mst, 0,sizeof edges_on_mst);
        memset(take_me,0,sizeof take_me);
        all_edges.clear();


        scc(nodes)
        scc(edges)

        int i, second_best_mst = INT_MAX;

        for(i = 1; i<= edges; i++)
        {
            int c,s,e;

            scc(s)
            scc(e)
            scc(c)

            all_edges.pb({c,{s,e}});
        }

        int cost_of_mst = mst();

        for(i=0;i<edges;i++)
        {
            if(edges_on_mst[i])
            {
                take_me[i] = 1;

                second_best_mst = min(second_best_mst , second_mst());

                take_me[i] = 0;
            }
        }

        printf("Case #%d : ",t++);

        if(cost_of_mst == -1)
        {
            puts("No way");
        }
        else if(second_best_mst == INT_MAX)
        {
            puts("No second way");
        }
        else
        {
            printf("%d\n",second_best_mst);
        }

    }

    return 0;
}