#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n,m,i,j,t[200005],w,ww,q,qq,r[400005],p[400005],s,u;
struct muchie
{
    int x,y,c;
};
muchie d[400005];


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;
        while(q!=t[q])
        {
            q=t[q];
        }
        qq=d[i].x;
        t[qq]=q;

        w=d[i].y;
        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++;
            r[u]=d[i].x;
            p[u]=d[i].y;
        }
    }
    out<<s<<'\n'<<u<<'\n';
    for(i=1;i<=u;i++)
        out<<r[i]<<' '<<p[i]<<'\n';

}