#include <bits/stdc++.h>
#define EMax 400000
#define NMax 200000
using namespace std;

struct apm{ int x,y,c; };
apm v[EMax+1];
int tata[NMax+1];
int solx[NMax+1];
int soly[NMax+1];
int N,M,K;

bool cmp(const apm A, const apm B)
{
    return A.c < B.c;
}

int Find(int x)
{
    int v,rad=x;
    while(tata[rad]) rad = tata[rad];
    while(tata[x])
    {
        v = tata[x];
        tata[x] = rad;
        x = v;
    }
    return rad;
}

void Union(int x, int y)
{
    tata[x] = y;
}

int main(){
    FILE* fin = fopen("apm.in","r");
    FILE* fout = fopen("apm.out","w");

    int i,t1,t2,res=0;

    fscanf(fin,"%d %d",&N,&M);
    for(i = 1; i <= M; ++i) fscanf(fin,"%d %d %d",&v[i].x,&v[i].y,&v[i].c);

    sort(v+1,v+M+1,cmp);
    for(i = 1; i <= M; ++i)
    {
        t1 = Find(v[i].x);
        t2 = Find(v[i].y);
        if(t1 != t2){
            Union(t1,t2);
            res += v[i].c;
            solx[++K] = v[i].x;
            soly[K] = v[i].y;
        }
    }

    fprintf(fout,"%d\n",res);
    fprintf(fout,"%d\n",K);
    for(i = 1; i <= K; ++i) fprintf(fout,"%d %d\n",solx[i],soly[i]);


return 0;
}