#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct hey{int x,y,c;}v[400001];
struct buna{int a,b;}fin[200001];
int w[200001],s,k;
bool cmp(hey a, hey b)
{
    if(a.c<b.c)
        return true;
    return false;
}
int boss(int a)
{
    if(w[a]==a)
        return a;
    return w[a]=boss(w[a]);
}
void calculam(int x, int y, int b)
{
    if(boss(x)!=boss(y))
    {
        w[boss(x)]=boss(y);
        k++;
        fin[k].a=x;
        fin[k].b=y;
        s=s+b;
    }
}
int main ()
{
    int N,M,X,Y,C,i;
    f>>N>>M;
    for(i=1;i<=M;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+M+1,cmp);
    for(i=1;i<=N;i++)
        w[i]=i;
    for(i=1;i<=M;i++)
    {
        calculam(v[i].x,v[i].y,v[i].c);
    }
    g<<s<<'\n';
    g<<k<<'\n';
     for(i=1;i<=k;i++)
        g<<fin[i].a<<" "<<fin[i].b<<" "<<'\n';
    return 0;
}