#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,i,j,s,t[200005],nr,p1,p2,r[200005];
struct krs
{
    int i,j,cost;
}v[400005],A[400005];
int cmp(krs a,krs b)
{
    return a.cost<b.cost;
}
int root(int nod)
{
    if(t[nod]==0) return nod;
    else return t[nod]=root(t[nod]);
}
void unite(int x,int y)
{
    int rx=root(x),ry=root(y);
    if(rx==ry) return;
    if(r[rx]>r[ry])
    {
        r[rx]+=r[ry];
        t[ry]=rx;
    }
    else
    {
        r[ry]+=r[rx];
        t[rx]=ry;
    }
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>v[i].i>>v[i].j>>v[i].cost;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        p1=root(v[i].i);
        p2=root(v[i].j);
        if(p1!=p2)
        {
            s+=v[i].cost;
            A[++nr]=v[i];
            unite(p1,p2);
        }
    }
    cout<<s<<'\n';
    cout<<n-1<<'\n';
    for(i = 1; i < n; i++)
        cout << A[i].i << " " << A[i].j << '\n';
    return 0;
}