#include <cstdio>
#include <cstdlib>
#define MaxN 200001
#define Inf 1005
using namespace std;
int N, M, i, j, CMin[MaxN], NLeft, Min, NodeMin[MaxN], Node, VMax, Show[MaxN];
int *A[MaxN], *C[MaxN];
int a, b, c;
bool Check[MaxN];
void Read();
void Afisare();
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    Read();
    CMin[1]=Inf; Check[1]=1;
    for(i=2; i<=N; ++i){
        CMin[i]=Inf;
        for(j=1; j<=A[i][0]; ++j)
            if(A[i][j]==1) {CMin[i]=C[i][j]; NodeMin[i]=1;}
    }
    NLeft=N-1;
    while(NLeft){
        --NLeft;
        Min=Inf;
        for(i=1; i<=N; ++i){
            if(CMin[i]<Min && !Check[i]){
                Min=CMin[i];
                Node=i;
            }
        }
        VMax+=Min;
        Show[Node]=NodeMin[Node];
        Check[Node]=1;
        for(i=1; i<=A[Node][0]; ++i){
            if(!Check[A[Node][i]] && C[Node][i]<CMin[A[Node][i]]){
                CMin[A[Node][i]]=C[Node][i];
                NodeMin[A[Node][i]]=Node;
            }
        }
    }
    Afisare();
    return 0;
}









































void Read(){
    scanf("%d%d", &N, &M);
    for(i=1; i<=N; ++i){
        A[i]=(int *)realloc(A[i], sizeof(int));
        A[i][0]=0;
        C[i]=(int *)realloc(C[i], sizeof(int));
        C[i][0]=0;
    }
    for(i=1; i<=M; ++i){
        scanf("%d%d%d", &a, &b, &c);
        ++A[a][0];
        A[a]=(int *)realloc(A[a], (A[a][0]+1)*sizeof(int));
        A[a][A[a][0]]=b;
        ++C[a][0];
        C[a]=(int *)realloc(C[a], (C[a][0]+1)*sizeof(int));
        C[a][C[a][0]]=c;
        ++A[b][0];
        A[b]=(int *)realloc(A[b], (A[b][0]+1)*sizeof(int));
        A[b][A[b][0]]=a;
        ++C[b][0];
        C[b]=(int *)realloc(C[b], (C[b][0]+1)*sizeof(int));
        C[b][C[b][0]]=c;
    }
    return;
}
void Afisare(){
    printf("%d\n%d\n", VMax, N-1);
    for(i=2; i<=N; ++i)
        printf("%d %d\n", i, Show[i]);
    return;
}