#include <bits/stdc++.h>

using namespace std;

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

int T[200005];
int n, m, k, x, y, t;

struct apm
{
    int i; int j; int cost;
} a[400005], res[200005];

int get_root(int nod)
{
    int tmp = nod;
    while(T[nod] > 0)
        nod = T[nod];
    int root = nod;
    nod = tmp;
    while(nod != root)
    {
        tmp = T[nod];
        T[nod] = root;
        nod = tmp;
    }
    return root;
}

bool cmp(const apm &x, const apm &y)
{
    return x.cost < y.cost;
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> a[i].i >> a[i].j >> a[i].cost;
    sort(a+1, a+m+1, cmp);
    for(int i = 1; i <= n; i++)
        T[i] = -1;
    int i = 0, k = 0;
    while(n-1 > k)
    {
        i++;
        x = get_root(a[i].i);
        y = get_root(a[i].j);
        if(x != y)
            if(T[x] < T[y])
            {
                t += a[i].cost;
                k++;
                res[k].i = a[i].i;
                res[k].j = a[i].j;
                T[x] += T[y];
                T[y] = x;
            }
            else
            {
                t += a[i].cost;
                k++;
                res[k].i = a[i].i;
                res[k].j = a[i].j;
                T[y] += T[x];
                T[x] = y;
            }
    }
    fout << t << '\n' << k << '\n';
    for(int i = 1; i <= k; i++)
        fout << res[i].j << " " << res[i].i << '\n';
    return 0;
}