#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, m, w[10000], v[200000], s = 0;

struct muchie
{
    int a, b, c;
};

muchie mu[400000];

bool cmp ( muchie x, muchie y )
{
    return x.c < y.c;
}

int main()
{
    fin >> n >> m;
    for ( int i = 1; i <=m; i ++ )
    {
        int x, y, z;
        fin >> x >> y >> z;
        mu[i].a = x;
        mu[i].b = y;
        mu[i].c = z;
    }
    sort ( mu + 1, mu + m + 1, cmp );

    for ( int i = 1; i <= n; i ++ )
        v[i] = i;

    for ( int i = 1; i <= m; i ++ )
        if ( v[mu[i].a] != v[mu[i].b] )
        {
            s += mu[i].c;
            w[i] = 1;
            for ( int j = 1; j <= n; j ++ )
            {
                int f = v[mu[i].b];
                if ( v[j] == f )
                    v[j] = v[mu[i].a];
            }
        }
    fout << s << "\n" << n - 1 << "\n";
    for ( int i = 1; i <= m; i ++ )
        if ( w[i] )
            fout << mu[i].a << " " << mu[i].b << "\n";
    return 0;
}