#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], Sum, j, Couple[MaxN], MaxC, k;
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];
    Show[1]=WorKList[1]; MaxC=1;
    Couple[WorKList[1].first]=Couple[WorKList[1].second]=MaxC; j=2;
    for(i=2; i<N; ++i){
        for(; j<=M; ++j){
            if(Couple[WorKList[j].second]!=Couple[WorKList[j].first]){
                if(Couple[WorKList[j].first]==0 || Couple[WorKList[j].second]==0){
                    if(Couple[WorKList[j].first]==0) Couple[WorKList[j].first]=Couple[WorKList[j].second];
                    else Couple[WorKList[j].second]=Couple[WorKList[j].first];
                }
                else{
                    int a=Couple[WorKList[j].first];
                    for(k=1; k<=N; ++k) if(Couple[k]==a) Couple[k]=Couple[WorKList[j].second];
                }
                Show[i]=WorKList[j];
                Sum+=WorkHeap[j];
                ++j;
                break;
            }
            else if(Couple[WorKList[j].first]==0){
                ++MaxC;
                Couple[WorKList[j].first]=Couple[WorKList[j].second]=MaxC;
                Show[i]=WorKList[j];
                Sum+=WorkHeap[j];
                ++j;
                break;
            }
        }

    }
    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){
    while(i>1 && Heap[i]<Heap[i/2]){
            swap(Heap[i], Heap[i/2]);
            PSwap(CList[i], CList[i/2]);
            i/=2;

    }
    return;
}
void Sift(int i){
    while((i*2<=Vf && Heap[i]>Heap[i*2]) || (i*2+1<=Vf && Heap[i]>Heap[i*2+1])){
            int a;
            if(Heap[i*2]<Heap[i*2+1])a=i*2;
            else a=i*2+1;
            swap(Heap[i], Heap[a]);
            PSwap(CList[i], CList[a]);
            i=a;
    }
}
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;
}