TSP

#include<bits/stdc++.h>
using namespace std;
#define D(x) cout<<#x<<" = " <<x<<endl
#define mx 10000
#define inf 1e9

vector<int> edge[mx];
int cost[mx][mx];
vector<int> new_mst[mx];
int arr[mx+5];
int n, m, t, u, v, w, idx = 0;

int parent[mx], visited[mx], value[mx];
map<int, string> mp;

void dfs(int src);
void solve();

struct Node
{
    int x, d;
}ND;

bool operator < (Node A, Node B)
{
    if(A.d<B.d) return false;
    return true;
}

void init()
{
    for(int i =0; i< mx; i++){
        edge[i].clear();
        new_mst[i].clear();
    }
    mp[0] = "Dhaka";
    mp[1] = "Rajsahi";
    mp[2] = "Khulna";
    mp[4] = "Barishal";
    mp[3] = "chattogram";
    mp[5] = "Syhlet";
}

void print()
{
    cout<<endl;
    D("MST ");
    int idx;
    for(int i =0 ; i< n;i++)
    {
        int p = parent[i];
        if(p == -1) cout<<"Root is "<<mp[i]<<endl, idx = i;
        else{
                cout<<mp[p]<<" to " <<mp[i]<<" = "<<value[i]<<endl;
                //printf(" %d to %d = %d\n",mp[p], mp[i], value[i]);
                new_mst[p].push_back(i);
        }
    }
    cout<<endl;
    memset(visited, 0, sizeof visited);
    dfs(idx);
    cout<<" "<<mp[0]<<endl;
    solve();
}

void mst(int src)
{
    memset(visited,0, sizeof visited);
    memset(parent, -1, sizeof parent);
    for(int i =0; i< n;i++) value[i] = inf;

    value[src] = 0;
    ND.x = src;
    ND.d = value[src];
    visited[src] = 1;

    priority_queue<Node> q;
    q.push(ND);

    while(!q.empty())
    {
        Node u;
        u = q.top();
        q.pop();
        visited[u.x] = 1;
        //printf("Node %d : %d",)
        for(int i = 0; i< edge[u.x].size(); i++)
        {
            Node v;
            v.x = edge[u.x][i];
            v.d = cost[u.x][v.x];
            //printf("Node %d to %d : %d\n",u.x,v.x,v.d);
            if(!visited[v.x] && value[v.x] > v.d)
            {
                value[v.x] = v.d;
                parent[v.x] = u.x;

                q.push(v);
            }
        }
    }
    print();
}


void dfs(int src)
{
    arr[idx++] = src;
    cout<<mp[src]<<" -> ";
   // printf("%s -> ", src);
    for(int i =0; i< new_mst[src].size(); i++)
    {
        dfs(new_mst[src][i]);
    }
}

void solve()
{
    cout<<endl;
    int ret = 0;
    arr[n] = 0;
    for(int i = 0; i< n;i++)
    {
        int q, ww;
        q = arr[i];ww = arr[i+1];
        cout<<mp[q]<<" -> " <<mp[ww]<<" = " <<cost[q][ww]<<endl;
        //printf("Edge %d to %d = %d\n",arr[i],arr[i+1],cost[arr[i]][arr[i+1]]);
        ret+=cost[arr[i]][arr[i+1]];
    }
    cout<<endl;
    D(ret);
}

int main()
{
    freopen("input.txt","r",stdin);
    cin>>t;
    while(t--)
    {
        init();
        cin>>n>>m;
        for(int i=0; i< m ;i++)
        {
            cin>>u>>v>>w;
            edge[u].push_back(v);
            edge[v].push_back(u);
            cost[u][v] = w;
            cost[v][u] = w;
        }
        mst(0);
    }

    return 0;
}



/* input
1
6 15
0 2 141
0 1 121
0 3 214
0 4 163
0 5 191
2 1 197
2 3 237
2 4 85
2 5 330
1 3 395
1 4 258
1 5 336
3 4 152
3 5 280
4 5 290

*/