#include <cstdio>
#include <cstdlib>
#define MaxN 200001
#define Inf 1005
#define swap(a, b){int aux; aux=a; a=b; b=aux;}
#define min(a, b)(a<b?a:b)
using namespace std;
int N, M, i, j, NLeft, Min, Node, VMax, Show[MaxN];
int *A[MaxN], *C[MaxN];
int a, b, c;
int Poz[MaxN], PHeap[MaxN];
bool Check[MaxN];
int Placed[MaxN];
int Heap[MaxN], vfheap;
void Read();
void Afisare();
void BuildHeap(int Heap[MaxN]);
void Sift(int j);
void Percolate(int j);
int main(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    Read();
    NLeft=N-1;
    Check[1]=1;
    for(i=1; i<=A[1][0]; ++i){
        Heap[++vfheap]=C[1][i];
        Show[A[1][i]]=1;
        Poz[vfheap]=A[1][i];
        Placed[A[1][i]]=vfheap;
    }
    BuildHeap(Heap);
    while(NLeft){
        --NLeft;
        Check[Poz[1]]=1;
        Node=Poz[1];
        VMax+=Heap[1];
        Heap[1]=Heap[vfheap];
        Placed[Poz[vfheap]]=Placed[Poz[1]];
        Poz[1]=Poz[vfheap];
        Sift(1);
        --vfheap;
        for(i=1; i<=A[Node][0]; ++i){
            if(!Check[A[Node][i]]){
                if(!Placed[A[Node][i]]){
                    Show[A[Node][i]]=Node;
                    Heap[++vfheap]=C[Node][i];
                    Poz[vfheap]=A[Node][i];
                    Placed[A[Node][i]]=vfheap;
                    Percolate(vfheap);
                }
                else if(C[Node][i]<Heap[Placed[A[Node][i]]]){
                    Heap[Placed[A[Node][i]]]=C[Node][i];
                    Show[A[Node][i]]=Node;
                    Percolate(Placed[A[Node][i]]);
                }
            }
        }
    }
    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;
}
void BuildHeap(int Heap[MaxN]){
    int j;
    for(i=vfheap/2; i>=1; --i){
    j=i;
    Sift(j);
    }
    return;
}
void Sift(int j){
    int a;
    while(j*2<=vfheap && (Heap[j*2]<Heap[j] || (Heap[j*2+1]<Heap[j] && j*2+1<=vfheap))){
         if(j*2+1>vfheap){
            swap(Heap[j], Heap[j*2]);
            swap(Placed[Poz[j]], Placed[Poz[j*2]]);
            swap(Poz[j], Poz[j*2]);
            j=j*2;
         }
         else{
            a=(Heap[j*2]<Heap[j*2+1]?j*2:j*2+1);
            swap(Heap[j], Heap[a]);
            swap(Placed[Poz[j]], Placed[Poz[a]]);
            swap(Poz[j], Poz[a]);
            j=a;
         }
    }
    return;
}
void Percolate(int j){
    while(j/2>=1 && Heap[j/2]>Heap[j]){
            swap(Heap[j], Heap[j/2]);
            swap(Placed[Poz[j]], Placed[Poz[j/2]]);
            swap(Poz[j], Poz[j/2]);
            j=j/2;}
    return;
}