#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

#define pb push_back

using namespace std;

const int NMax= 400100;

int GR[NMax], X[NMax], Y[NMax], C[NMax], vec[NMax];
int N,M;
int Ans[NMax];

void Read()
{
    scanf("%d%d",&N,&M);

    for(int i=1; i<=M; ++i)
    {
        scanf("%d%d%d\n", &X[i], &Y[i], &C[i]);
        vec[i]=i;
    }

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

bool Compare(int i, int j)
{
    return (C[i] < C[j]);
}

int radacina(int i)
{
    if(GR[i]==i)
        return i;

    GR[i]=radacina(GR[i]);

    return GR[i];
}

void reuniune(int i,int j)
{
    GR[radacina(j)]=radacina(i);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    Read();

    sort(vec+1, vec+M+1 ,Compare);

    int cost=0, sol=0;
    for(int i=1; i<=M ; ++i)
    {
        if(radacina(X[vec[i]]) != radacina(Y[vec[i]]))
        { sol++;
            cost+=C[vec[i]];
            reuniune(X[vec[i]] , Y[vec[i]]);
            Ans[sol]=vec[i];
        }
    }

    printf("%d\n", cost);
    printf("%d\n", N-1);

    for(int i=1; i<N ; ++i)
        printf("%d %d\n", X[Ans[i]], Y[Ans[i]]);


    return 0;
}