#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int k=0,n,m,i,x,y,c,cf=0,tata[200010];
struct kl
{
    int a,b,cst;
}t[200010];
struct ceva
{
    int a,b;
}v[200010];
int fnd(int x)
{
    int y,aux=x;
    while(tata[x]!=x)
        x=tata[x];
    while(aux!=x)
    {
        y=tata[aux];
        tata[aux]=x;
        aux=y;
    }
    return x;
}
void unite(int x, int y)
{
    x=fnd(x);
    y=fnd(y);
    tata[x]=y;
}
int cmp(kl x, kl y)
{
    return (x.cst<y.cst);
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>t[i].a>>t[i].b>>t[i].cst;
    for(i=1;i<=n;i++)
        tata[i]=i;
    sort(t+1,t+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        if(fnd(t[i].a)!=fnd(t[i].b))
        {
            unite(t[i].a,t[i].b);
            cf+=t[i].cst;
            v[++k].a=t[i].a;
            v[k].b=t[i].b;
        }
    }
    fout<<cf<<'\n';
    fout<<k<<'\n';
    for(i=1;i<=k;i++)
        fout<<v[i].a<<' '<<v[i].b<<'\n';

    return 0;
}