#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie {int x,y,c;} v[400001];
int T[200001],RG[200001],n,m,nr,sol[200001],sum;
bool Cmp(muchie a, muchie b)
{
    if(a.c<b.c)
        return 1;
    return 0;
}
int Find(int x)
{
    int R,y;
    for (R = x; T[R] != R; R = T[R]);
    for (;T[x]!=x;)
    {
        y=T[x];
        T[x]=R;
        x=y;
    }
    return R;
}

void unite(int x, int y)
{
    if (RG[x]>RG[y])
        T[y]=x;
    else
        T[x]=y;
    if(RG[x]==RG[y])
        RG[y]++;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        T[i]=i;
        RG[i]=1;
    }
    for(int i=1;i<=m;++i)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,Cmp);
    for(int i=1;nr<n-1;i++)
        if(Find(v[i].x)!=Find(v[i].y))
        {
            sol[++nr]=i;
            sum+=v[i].c;
            unite(Find(v[i].x),Find(v[i].y));
        }
    g<<sum<<'\n'<<nr<<'\n';
    for(int i=1;i<=nr;++i)
        g<<v[sol[i]].x<<' '<<v[sol[i]].y<<'\n';
    return 0;
}