#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int N,M,a[200000],u,R;
struct muchie
{
    int x,y,c;
}m[400000];
struct solutie
{
    int x,y;
}sol[200000];

int cmp(muchie m1,muchie m2)
{
    return m1.c<m2.c;
}
int main()
{
    in>>N>>M;
    int i,xx,yy,q,j;
    for(i=1;i<=M;++i)
    {
        in>>m[i].x>>m[i].y>>m[i].c;
    }
    sort(m+1,m+M+1,cmp);
    for(i=1;i<=N;++i) a[i]=i;
    for(i=1;i<=M;++i)
    {
        xx=m[i].x;
        yy=m[i].y;
        if(a[xx]!=a[yy])
        {
            q=a[yy];
            for(j=1;j<=N;++j) if(a[j]==q) a[j]=a[xx];
            sol[++u].x=xx;
            sol[u].y=yy;
            R+=m[i].c;
        }
    }
    out<<R<<'\n'<<u<<'\n';
    for(i=1;i<=u;++i)
    {
        out<<sol[i].x<<' '<<sol[i].y<<'\n';
    }
}