#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");  // strudel
ofstream fout("apm.out");// apm
int n,m,i,s;
struct aaa{
    int x,y,c;
};
aaa a[400010];
int t[200010];
vector<pair<int,int>> rez;
bool cmp(aaa a,aaa b){
    return a.c<b.c;
}
int getp(int x){
    if(t[x]>0) t[x]=getp(t[x]), x=t[x];
    return x;
}
void joinn(int x, int y, int c){
    int px=getp(x),py=getp(y);
    if(px!=py){
        rez.push_back({x,y}), s+=c;
        if(-t[py]>t[px]) swap(px,py);
        t[px]+=t[py];
        t[py]=px;
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++) fin>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;i++){
        joinn(a[i].x,a[i].y,a[i].c);
    }
    fout<<s<<'\n'<<rez.size()<<'\n';
    for(auto it:rez) fout<<it.first<<" "<<it.second<<'\n';
    return 0;
}