#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

const int maxim = 400100;
int *C;//[maxim];
//C=new int[maxim];

int grupa(int i,int G[])
{
    if (G[i] == i) return i;
    G[i] = grupa(G[i],G);
    return G[i];
}

void reuniune(int i,int j,int G[])
{
    G[grupa(i,G)] = grupa(j,G);
}

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

int main()
{
    //const int maxim = 400100;
    int *G;//[maxim],
    int *X;//[maxim],
    int *Y;//[maxim];
    G=new int[maxim];
    X=new int[maxim];
    Y=new int[maxim];
    C=new int[maxim];
    int N,M,ANS,indice[maxim];
    vector<int> V;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&N,&M);
    for(int i = 1;i <= M;++i)
    {
        scanf("%d %d %d\n",&X[i],&Y[i],&C[i]);
        indice[i] = i;
    }

    for(int i = 1;i <= N; ++i) G[i] = i;
    sort(indice + 1,indice + M + 1,cmpf);
    for(int i = 1;i <= M; ++i)
    {
        if (grupa(X[indice[i]],G) != grupa(Y[indice[i]],G)){
            ANS += C[indice[i]];
            reuniune(X[indice[i]],Y[indice[i]],G);
            V.push_back(indice[i]);
        }
    }
    printf("%d\n",ANS);
    printf("%d\n",N - 1);
    for(int i = 0;i < N - 1; ++i)
        printf("%d %d\n",X[V[i]],Y[V[i]]);
    return 0;
}