//#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int tata[200005],sz[200005];
struct muchie{
    int x,y,c;
}v[400005];
bool mysort(muchie a, muchie b){
    return a.c<b.c;
}
long long union_find(int a){
    int cp=a;
    while(tata[a]!=a)
        a=tata[a];
    while(tata[cp]!=cp){
        int x=tata[cp];
        tata[cp]=a;
        cp=x;
    }
    return a;
}
void unite(int a,int b){
    a=union_find(a);
    b=union_find(b);
    if(sz[a]>sz[b]){
        tata[b]=a;
        sz[a]+=sz[b];
    }
    else{
        tata[a]=b;
        sz[b]+=sz[a];
    }
}
int sol[200005];
ifstream cin("apm.in");
ofstream cout("apm.out");
int main()
{
    int n,m,x,y,c,sum=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>c;
        v[i].x=x;
        v[i].y=y;
        v[i].c=c;
    }
    sort(v+1,v+m+1,mysort);
    int cnt=0;
    for(int i=1;i<=n;i++){
        tata[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<=m;i++){
        if(union_find(v[i].x)!=union_find(v[i].y)){
            unite(v[i].x,v[i].y);
            sum+=v[i].c;
            sol[++cnt]=i;
        }
    }
    cout<<sum<<"\n"<<n-1<<"\n";
    for(int i=1;i<=cnt;i++){
        cout<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
    }
    return 0;
}