#include <algorithm>
#include<fstream>
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
struct MUCHIE{
    int x, y, c;
}M[400001];
int culoare[250001], NRV[250001];
int n, m;

bool comp( MUCHIE a, MUCHIE b ){
    return a.c < b.c;
}

int stramos( int x ){
    int start;
    start = x;
    while( culoare[x] != x )
        x = culoare[x];
    while( start != x )
        start = culoare[start];
    return x;
}

int main()
{
    int i, poz, sum, ny, nx;
    fi >> n >> m;

    for( i = 1; i <= m; i++ )
        fi >> M[i].x >> M[i].y >> M[i].c;
    sort(M+1, M+m+1,comp );

    for( i = 1; i <= n; i++ ){
        culoare[i] = i;
        NRV[i] = 1;
    }

    poz = 1;
    sum = 0;
    for( i = 1; i <= n - 1; i++  ){
        while( stramos(M[poz].x) == stramos(M[poz].y) )
            poz++;
        nx = stramos(M[poz].x);
        ny = stramos(M[poz].y);
        if( nx <= ny ){
            NRV[ny] += NRV[nx];
            culoare[nx] = culoare[ny];
        }
        else{
            NRV[nx] += NRV[ny];
            culoare[ny] = culoare[nx];
        }


        sum += M[poz].c;
        M[i] = M[poz];
        poz++;
    }

    fo << sum << "\n" << n-1 << "\n";
    for( i = 1; i <= n - 1; i++ )
        fo << M[i].x << " " << M[i].y << "\n";

    return 0;
}