modern

#include <bits/stdc++.h>

using namespace std;

ifstream fin("modern.in");
ofstream fout("modern.out");

int parent[110], rnk[110], dist[110], c[110], p[110];

struct date
{
    int t, cost;
};

struct da
{
    int f, t, cost;
};

bool comp(da a, da b)
{
    return a.cost < b.cost;
}

vector < date > l[110];
vector < da > v;

int n, m, cT, maxim, loc;

queue < int > q;

int ufind(int nod)
{
    while (parent[nod] != nod)
    {
        parent[nod] = parent[parent[nod]];
        nod = parent[nod];
    }

    return nod;
}

void unite(int a, int b)
{
    if (rnk[a] > rnk[b])
        parent[b] = a;
    else
        parent[a] = b;

    if (rnk[a] == rnk[b])
        rnk[b]++;
}

void Kruskal()
{
    for (da el : v)
    {
        int rootF = ufind(el.f), rootT = ufind(el.t);

        if (rootF != rootT)
        {
            l[el.f].push_back({el.t, el.cost});

            cT += el.cost;
            unite(rootT, rootF);
        }
    }
}

void Bfs(int nod)
{
    dist[nod] = 1;
    c[nod] = 1;
    q.push(nod);

    while (!q.empty())
    {
        nod = q.front();
        q.pop();

        for (date el : l[nod])
        {
            q.push(el.t);

            p[el.t] = nod;

            if (!dist[el.t])
            {
                c[el.t] = c[nod] + 1;
                dist[el.t] = dist[nod] + el.cost;
            }

            if (dist[el.t] > maxim)
            {
                maxim = dist[el.t];
                loc = el.t;
            }

        }
    }
}

void Drum(int nod)
{
    if(p[nod])
        Drum(p[nod]);

    fout << nod << ' ';
}

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int a, b, c;

        fin >> a >> b >> c;

        v.push_back({a, b, c});
    }

    sort(v.begin(), v.end(), comp);

    for (int i = 1; i <= n; i++)
        parent[i] = i, rnk[i] = 1;


    Kruskal();

    for (int i = 1; i <= n; i++)
        for (date el : l[i])
            fout << i << ' ' << el.t << '\n';


    fout << cT * 100 << '\n';

    Bfs(1);

    fout << loc << ' ' << maxim - 1 << ' ' << c[loc] << '\n';

    Drum(loc);

    fin.close();
    fout.close();
    return 0;
}