#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int nr, legaturi, t[200005], tine, a, b, total, contor, raspuns[800010];

struct Drum
{
    int a, b, c;
}drum[200005];

bool functie(Drum a, Drum b)
{
    return a.c < b.c;
}

int rad(int x)
{
    if(t[x] == 0)
    return x;
    else
    {
        tine = rad(t[x]);
        t[x] = tine;
        return tine;
    }
}

int main()
{
    cin >> nr >> legaturi;
    for(int i=1; i <= legaturi; i++)
    {
        cin >> drum[i].a >> drum[i].b >> drum[i].c;
    }
    sort(drum+1, drum+legaturi+1, functie);

    for(int i=1; i <= legaturi; i++)
    {
        a = rad(drum[i].a);
        b = rad(drum[i].b);
        if(a != b)
        {
            contor++;
            raspuns[contor] = drum[i].a;
            contor++;
            raspuns[contor] = drum[i].b;

            t[a] = b;
            total += drum[i].c;
        }
    }
    cout << total << '\n';
    cout << contor/2 << '\n';
    for(int i=1; i <= contor; i++)
    {
        cout << raspuns[i];
        if(i % 2 == 1)
        cout << ' ';
        else
        cout << '\n';
    }
}