#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muc
{
        int x;
        int y;
        int c;
} l[400001];
struct nod
{
    int x;
    int y;

}sup[400001];
int n,m,i,j,x1,n1,nr;
int r[200001],t[200001];
long int cost;
int cmp(muc a, muc b)
{
    return a.c<b.c;
}
void read()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>l[i].x>>l[i].y>>l[i].c;
    }
    sort(l+1,l+m+1,cmp);
    for(i=1;i<=n;i++)
    {
        r[i]=i;
        t[i]=1;
    }

}
int cautxsauy(int x)
{
    if(r[x]==x)
    return x;
    return cautxsauy(r[x]);
}
void haidesapornim()
{
    j=0;
    for(i=1;i<=m;i++)
    {
        x1=cautxsauy(l[i].x);
        n1=cautxsauy(l[i].y);
        if(x1==n1)
        continue;
        if(t[x1]>=t[n1])
        {
            t[x1]+=t[n1];
            r[n1]=x1;
        }
        else
        {
            t[n1]+=t[x1];
            r[x1]=n1;
        }
        j++;
        sup[j].x=l[i].x;
        sup[j].y=l[i].y;
        cost+=l[i].c;
    }
    g<<cost<<"\n";
    g<<j<<"\n";
    for(i=1;i<=j;i++)
    g<<sup[i].x<<" "<<sup[i].y<<"\n";

}
int main()
{
 read();
    haidesapornim();
 return 0;
}