#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,a,b,sol,k,t[200005],s[400005];
struct muchie {
    int x,y,cost;
}v[400005];

bool cmp(muchie a,muchie b) {
    return a.cost<b.cost;
}

int rad(int nod) {
    while (t[nod]>0)
        nod=t[nod];
    return nod;
}

int main() {
    fin>>n>>m;
    for (int i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].cost;
    sort(v+1,v+m+1,cmp);
    for (int i=1;i<=n;i++)
        t[i]=-1;
    for (int i=1;i<=m;i++) {
        a=rad(v[i].x);
        b=rad(v[i].y);
        if (a!=b) {
            if (-t[a]>-t[b]) {
                t[a]+=t[b];
                t[b]=a;
            }
            else {
                t[b]+=t[a];
                t[a]=b;
            }
            sol+=v[i].cost;
            s[++k]=i;
        }
    }
    fout<<sol<<"\n"<<k<<"\n";
    for (int i=1;i<n;i++)
        fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
    return 0;
}