#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MaxN 200005
#define MaxM 400005
#define min(x, y) (x<y?x:y)
#define swap(x, y) {int aux; aux=x; x=y; y=aux;}
using namespace std;
int i, N, M, Heap[MaxM], Vf, WorkHeap[MaxM], V, Sum, j, Fq[MaxN];
bool Find[MaxN];
struct Pair{
    int first;
    int second;
}P;
#define PSwap(x, y) {Pair aux; aux=x; x=y; y=aux;}
Pair CList[MaxM];
Pair WorKList[MaxM];
Pair Show[MaxN];
void Read_Sort();
void HeapSort();
void Sift(int i);
void Percolate(int i);
void ReadString(int &a, int &b, int &c, bool Third);
void CharToInt(char *C, int &N);
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    Read_Sort();
    Sum=WorkHeap[1];
    V=2; Fq[WorKList[1].first]=Fq[WorKList[1].second]=1;
    Show[1]=WorKList[1];
    for(i=2; i<N; ++i){
        for(j=V; j<=M; ++j){
            if(Fq[WorKList[j].first]!=Fq[WorKList[j].second]){
                Sum+=WorkHeap[j];
                Fq[WorKList[j].first]=Fq[WorKList[j].second]=1;
                Show[i]=WorKList[j];
                break;
            }
        }
        if(!Show[N-1].first)while(Fq[WorKList[V].first]==1 && Fq[WorKList[V].first]==Fq[WorKList[V].second])++V;
    }
    printf("%d\n%d\n", Sum, N-1);
    for(i=1; i<N; ++i)printf("%d %d\n", Show[i].first, Show[i].second);
    return 0;
}
void Read_Sort(){
    int Plus;
    ReadString(N, M, Plus, 0);
    Vf=M;
    for(i=1; i<=M; ++i){
        int x, y, z;
        ReadString(x, y, z, 1);
        CList[i].first=x;
        CList[i].second=y;
        Heap[i]=z;
        Percolate(i);
    }

    for(i=1; i<M; ++i){
        WorkHeap[i]=Heap[1];
        WorKList[i]=CList[1];
        Heap[1]=Heap[Vf];
        CList[1]=CList[Vf];
        Vf--;
        Sift(1);
    }
    WorkHeap[M]=Heap[1];
    WorKList[M]=CList[1];

    return;
}
void Percolate(int i){
    bool k=0;
    while(i>1 && k==0){
        k=1;
        if(Heap[i/2]>Heap[i]){
            swap(Heap[i], Heap[i/2]);
            PSwap(CList[i], CList[i/2]);
            i/=2;
            k=0;
        }
    }
    return;
}
void Sift(int i){
    bool k=0;
    while(i*2<=Vf && k==0){
        k=1;
        if(i*2==Vf && Heap[i]>Heap[i*2]){
            swap(Heap[i], Heap[i*2]);
            PSwap(CList[i], CList[i*2]);
            i*=2;
            k=0;
        }
        else if(Heap[i]>min(Heap[i*2], Heap[i*2+1])){
            int a=(Heap[i*2]<Heap[i*2+1]?i*2:i*2+1);
            swap(Heap[i], Heap[a]);
            PSwap(CList[i], CList[a]);
            i=a;
            k=0;
        }
    }
}
void ReadString(int &a, int &b, int &c, bool Third){
    char C[1001], *P;
    fgets(C, 1001, stdin);
    P=strtok(C, " ");
    CharToInt(P, a);
    if(!Third){
        P=strtok(NULL, "\n");
        CharToInt(P, b);
        return;
    }
    P=strtok(NULL, " ");
    CharToInt(P, b);
    P=strtok(NULL, "\n");
    CharToInt(P, c);
    return;
}
void CharToInt(char *C, int &N){
    int L=strlen(C);
    int i; N=0;
    int sign;
    if(C[0]=='-'){
        i=1; sign=-1;
    }
    else {
        i=0; sign=1;
    }
    for(; i<L; ++i) N=N*10+(C[i]-'0');
    N=N*sign;
    return;
}