#include <bits/stdc++.h>

using namespace std;

#define MAXN 200001
#define MAXM 400001

ifstream f("apm.in");
ofstream g("apm.out");

int N,M,sel,cost;
int grupa[MAXN];

struct muchie
{
    int x,y,c;
}V[MAXM],sol[MAXM];

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

int main()
{
    f >> N >> M;
    for ( int i = 1; i <= M; i++ ) f >> V[i].x >> V[i].y >> V[i].c ;
    sort(V+1,V+M+1,criteriu);

    for ( int i = 1; i <= N; i++ ) grupa[i]=i;

    for ( int i = 1; i <= M and sel < N; i++ )
    {
        if ( grupa[V[i].x] != grupa[V[i].y] )
        {
            cost+=V[i].c;
            sel++;
            sol[sel] = V[i];
            int mn = min(grupa[V[i].x],grupa[V[i].y]);
            int mx = max(grupa[V[i].x],grupa[V[i].y]);
            for ( int j = 1; j <= N; j++ )
                if ( grupa[j] == mx )
                    grupa[j] = mn;
        }
    }

    g << cost << "\n" << N-1 << "\n" ;
    for ( int i = 1; i <= N-1; i++ )
        g << sol[i].x << " " << sol[i].y << "\n" ;


    return 0;
}