#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int x, y, c;
}v[400005], memorare[400005];

int n, m, l[200005], k, i, cnt, nr1, nr2;
long long cst;

bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}

int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i++)
        f >> v[i].x >> v[i].y >> v[i].c;
    sort(v + 1, v + m + 1, cmp);
    for(int i = 1; i <= n; i++)
        l[i] = i;
    k = 0, i = 1;
    while(k < n - 1)
    {
        if(l[v[i].x] != l[v[i].y])
        {
            k++;
            cst += v[i].c;
            memorare[k].x = v[i].x;
            memorare[k].y = v[i].y;
            nr1 = l[v[i].x];
            nr2 = l[v[i].y];
            for(int j = 1; j <= n; j++)
                if(l[j] == nr2)
                    l[j] = nr1;
        }
        i++;
    }
    g << cst << endl << k << endl;
    for(i = 1; i <= k; i++)
        g << memorare[i].x << " " << memorare[i].y << endl;

    return 0;
}