#include <bits/stdc++.h>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int T[200010], n, m, cost, i, x, y, z, k, a, b;
pair<int, int> sol[200010];
pair<int, pair<int, int> > E[400010];

int compresie(int x)
{
    if(T[x] == x) return x;
    T[x] = compresie(T[x]);
    return T[x];
}

int main()
{
    f >> n >> m;
    for(i = 1; i <= n; i++)
        T[i] = i;
    for(i = 1; i <= m; i++)
    {
        f >> x >> y >> z;
        E[i] = {z, {x, y}};
    }
    sort(E+1, E+m+1);

    for(i = 1; i <= m && k < n-1; i++)
    {
        a = E[i].second.first;
        b = E[i].second.second;
        x = compresie(a);
        y = compresie(b);
        if(x == y) continue;
        cost += E[i].first;
        T[x] = y;
        sol[++k] = {a, b};
    }
    g << cost << '\n' << k << '\n';
    for(i = 1; i <= k; i++)
        g << sol[i].first << ' ' << sol[i].second << '\n';
    return 0;
}