#include <stdio.h>
#include <algorithm>
#define nod 200005
#define muchie 400005
using namespace std;
struct legaturi{int x,y,cost;};
legaturi v[muchie];
bool cmp(legaturi a,legaturi b){
    if(a.cost<b.cost)
        return true;
    return false;
}
int boss[nod],rasp[muchie];
int tata(int a){
    if(boss[a]==a)
        return a;
    boss[a]=tata(boss[a]);
    return boss[a];
}
void unire(int a,int b){
    int ra=tata(a);
    int rb=tata(b);
    boss[ra]=rb;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    int i,n,m,k=0,suma=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].cost);
    for(i=1;i<=n;i++)
        boss[i]=i;
    sort(v+1,v+m+1,cmp);
    n=n*2;
    for(i=1;i<=m&&k<n;i++)
        if(boss[tata(v[i].x)]!=boss[tata(v[i].y)]){
            suma+=v[i].cost;
            unire(v[i].x,v[i].y);
            k++;
            rasp[k]=v[i].x;
            k++;
            rasp[k]=v[i].y;
        }
    k=k/2;
    fprintf(fout,"%d\n%d\n",suma,k);
    for(i=1;i<=k;i++)
        fprintf(fout,"%d %d\n",rasp[2*i-1],rasp[2*i]);
    fclose(fin);
    fclose(fout);
    return 0;
}