#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,t[200008],muci[2][400080],cst,k,rang[100021],i;
struct muchie
{
    int i,j,c;
}x[400008],aux;
int r(int c)
{
    if(t[c]!=0)
        {
            int k=r(t[c]);
            t[c]=k;
            return k;
        }
        return c;

}
void unire(int z, int y)
{
    int rx=r(z), ry=r(y);
    if(rx!=ry)
    {
        cst+=x[i].c;
        muci[0][++k]=z;
        muci[1][k]=y;
        if(rang[rx]>rang[ry])
            t[ry]=rx;
        else
        {
            t[rx]=ry;
            if(rang[z]==rang[y])
                rang[y]++;
        }
    }
}
bool cmp(muchie i, muchie j)
{
    return(i.c<j.c);
}
int main()
{
    int j;
    in>>n>>m;
    for(i=1;i<=m;i++)
        in>>x[i].i>>x[i].j>>x[i].c;
   sort(x+1,x+m+1,cmp);
   for(i=1;i<=m;i++)
   {
        unire(x[i].i, x[i].j);
   }
   out<<cst<<'\n'<<k<<'\n';
   for(i=1;i<=k;i++)
    out<<muci[0][i]<<' '<<muci[1][i]<<'\n';
    return 0;
}