#include <iostream>
#include <fstream>
#include <vector>
#include<cstdio>
#include <algorithm>
#define MAX_N 200010

using namespace std;

int  ACM[2*MAX_N];
int X[2*MAX_N], Y[2*MAX_N], C[2*MAX_N], R[MAX_N], Ind[MAX_N];
int cost_apm;

int comp_conexa(int a)
{
    if(R[a] == a)
        return a;
    R[a] = comp_conexa(R[a]);
    return R[a];
}

void reuniune(int a, int b)
{
    R[comp_conexa(a)] = comp_conexa(b);
}

bool sortare(int x, int y)
{
    return (C[x] < C[y]);
}

int main()
{
    int N, M, i, x, y, c,nrsol=0;
    freopen ("apm.in", "r", stdin);
    scanf("%d%d", &N, &M);
    for(i = 1; i <= M; i++)
    {
       // f >> X[i] >> Y[i] >> C[i];
        scanf("%d%d%d", &X[i], &Y[i],&C[i]);
        Ind[i] = i;
        R[i] = i;
    }
    sort(Ind+1, Ind+M+1, sortare);
    for(i = 1; i <= M; i++)
    {
        if(comp_conexa(X[Ind[i]]) != comp_conexa(Y[Ind[i]]))
        {
            cost_apm += C[Ind[i]];
            reuniune(X[Ind[i]], Y[Ind[i]]);
            ACM[++nrsol]=Ind[i];
        }
    }
    freopen ("apm.out", "w", stdout);
    //g << cost_apm << endl << N-1 <<endl;
    printf("%d\n%d\n", cost_apm, N-1);
    for(i = 1; i <= nrsol; i++)
        printf("%d %d\n", X[ACM[i]], Y[ACM[i]]);
    //g<<X[ACM[i]]<<" "<<Y[ACM[i]]<<endl;
    return 0;
}