#include<iostream>
#include<fstream>
#include<set>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int N,M,a[200000],u,R,t[200000];
bool viz[200000];
struct muchie
{
    int x,y,c;
}m;
struct solutie
{
    int x,y;
}sol[200000];
multiset <muchie> s;
multiset <muchie> :: iterator it;
bool operator < (muchie m1, muchie m2)
{
    return m1.c<m2.c;
}
int tata(int i);
int main()
{
    in>>N>>M;
    int i,xx,yy,q,tx,ty;
    for(i=1;i<=M;++i)
    {
        in>>m.x>>m.y>>m.c;
        s.insert(m);
    }
    for(i=1;i<=N;++i) t[i]=i;
    for(it=s.begin();it!=s.end();++it)
    {
        xx=it->x;
        yy=it->y;
        ty=tata(yy);
        tx=tata(xx);
        if(tx!=ty)
        {
            //q=a[yy];
            //for(i=1;i<=N;++i) if(a[i]==q) a[i]=a[xx];
            t[tx]=ty;
            sol[++u].x=xx;
            sol[u].y=yy;
            R+=it->c;
        }
    }
    out<<R<<'\n'<<u<<'\n';
    for(i=1;i<=u;++i)
    {
        out<<sol[i].x<<' '<<sol[i].y<<'\n';
    }
}
int tata(int i)
{
    if(t[i]==i) return i;
    return tata(t[i]);
}