#include <bits/stdc++.h>
#define M 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct elem
{
    int x,y,c;
}q[M],sol[M];
int n,m,i,j,mn=-2e9,x,y,c,s,l,e,t[M];
bool cmp(elem a,elem b)
{
    return a.c<b.c;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
      fin>>q[i].x>>q[i].y>>q[i].c;
      if(q[i].x>q[i].y) swap(q[i].x,q[i].y);
    }
    sort(q+1,q+m+1,cmp);
    for(i=2;i<=n;++i)
    {
        t[i]=i;
    }
    for(j=1;j<=m;++j)
    {
        x=q[j].x;
        y=q[j].y;
        c=q[j].c;
        e=t[y];
        if(t[x]!=t[y])
        {
            for(i=1;i<=n;++i)
            {
                if(t[i]==e)
                {
                    t[i]=t[x];
                }
            }
            s+=c;
            ++l;
            sol[l].x=x;
            sol[l].y=y;
        }
        if(l==n-1) break;
    }
    fout<<s<<'\n'<<l<<'\n';
    for(i=1;i<=l;++i)
    {
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';
    }
    return 0;
}