#include<iostream>
#include<fstream>
#include<set>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int N,M,a[200000],u,R;
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 main()
{
    in>>N>>M;
    int i,xx,yy,q;
    for(i=1;i<=M;++i)
    {
        in>>m.x>>m.y>>m.c;
        s.insert(m);
    }
    for(i=1;i<=N;++i) a[i]=i;
    for(it=s.begin();it!=s.end();++it)
    {
        xx=it->x;
        yy=it->y;
        if(a[xx]!=a[yy])
        {
            q=a[yy];
            for(i=1;i<=N;++i) if(a[i]==q) a[i]=a[xx];
            sol[++u].x=xx;
            sol[u].y=yy;
            R+=it->c;
            //cout<<xx<<' '<<yy<<'\n';
        //for(i=1;i<=N;++i) cout<<a[i];
        //cout<<'\n';
        }
    }
    out<<R<<'\n'<<u<<'\n';
    for(i=1;i<=u;++i)
    {
        out<<sol[i].x<<' '<<sol[i].y<<'\n';
    }
}