#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");


struct da
{
    int x,y,c;
}v[1000002];

int n,m,i,n1,n2,nr1,nr2,repr[1000002],cate,vec1[1000002],vec2[100002];
int costmin;

int crit(da t,da i)
{
    return (t.c<i.c);
}

int Find(int nod)
{
    if(repr[nod]==nod)
        return nod;
    else
    {
        repr[nod]=Find(repr[nod]);
        return repr[nod];
    }
}
void Unite(int a,int b)
{
    repr[a]=b;
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+1+m,crit);
    for(i=1;i<=n;i++)
        repr[i]=i;
    for(i=1;i<=m and cate<n-1;i++)
    {
        nr1=Find(v[i].x);
        nr2=Find(v[i].y);
        repr[n1]=nr1;
        repr[n2]=nr2;
        if(nr1!=nr2)
        {
            vec1[++cate]=v[i].x;
            vec2[cate]=v[i].y;
            costmin+=v[i].c;
            Unite(nr1,nr2);
        }
    }
    fout<<costmin<<'\n'<<cate<<'\n';
    for(i=1;i<=cate;i++)
        fout<<vec1[i]<<' '<<vec2[i]<<'\n';
    return 0;
}