#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct muchie
{
    int x,y,c;
};
muchie d[400005];
int n,m,i,j,q,w,qq,ww,u;
int t[200005],xx[400005],yy[400005],s;
bool cmp(muchie a, muchie b)
{
    return a.c<b.c;
}
int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>d[i].x>>d[i].y>>d[i].c;
    }
    sort(d+1,d+m+1,cmp);

    for(i=1;i<=n;i++)
        t[i]=i;
    for(i=1;i<=m;i++)
    {
        q=d[i].x;
        w=d[i].y;
        while(q!=t[q])
        {
            q=t[q];
        }
        qq=d[i].x;
        t[qq]=q;
        while(w!=t[w])
        {
            w=t[w];
        }
        ww=d[i].y;
        t[ww]=w;
        if(q!=w)
        {
            t[q]=w;
            s=s+d[i].c;
            u++;
            xx[u]=d[i].x;
            yy[u]=d[i].y;
        }
    }
    out<<s<<'\n'<<u<<'\n';
    for(i=1;i<=u;i++)
    {
        out<<xx[i]<<' '<<yy[i]<<'\n';
    }
}