/// #bettercoderthanshebeautiful
/// Minimum spanning tree
#include<bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
int t[200002],ans[200002];
struct muchii
{
    int a,b,c;
};
muchii v[400002];
bool cmp(muchii a, muchii b)
{
    return a.c<b.c;
}
int arb(int x)
{
    if(t[x]==x)
        return x;
    else
        return t[x]=arb(t[x]);
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
        f>>v[i].a>>v[i].b>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;++i)
        t[i]=i;
    long long s=0;
    int nr=0;
    for(int i=1;i<=m;i++)
        if(arb(v[i].a)!=arb(v[i].b))
        {
            t[arb(v[i].a)]=v[i].b;
            s+=v[i].c;
            ans[++nr]=i;
        }
    g<<s<<'\n'<<nr<<'\n';
    for(int i=1;i<=nr;i++)
        g<<v[ans[i]].a<<" "<<v[ans[i]].b<<'\n';
    return 0;
}