#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define nmax 200002
int n,i;
struct muchie {int x,y,c;} v[2*nmax],sol[2*nmax];
int t[2*nmax],m,k,cost;
void citire ()
{
    ifstream f ("apm.in");
    f>>n>>m;
    for (i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    f.close ();
}
int indvalmin (int i, int n)
{
    if (2*i+1<=n)
        if(v[2*i].c<v[2*i+1].c)
            return 2*i;
        else
            return 2*i+1;
    else
        return 2*i;
}
void combinare (int i, int n)
{
    int ind;
    muchie aux;
    if (i<=n/2)
        {
            ind=indvalmin(i,n);
            if (v[i].c>v[ind].c)
                {
                    aux=v[i];
                    v[i]=v[ind];
                    v[ind]=aux;
                    combinare (ind,n);
                }
        }
}
int radacina(int nod)
{
    if (t[nod]==0)
        return nod;
    else {
        t[nod]=radacina(t[nod]);
        return t[nod];
    }
}
void krusk()
{
    int i,tx,ty;
    for (i=1; i<=m; i++)
    {
        tx=radacina(v[i].x);
        ty=radacina(v[i].y);
        if (tx!=ty) {
            t[tx]=ty;
            k++;
            sol[k].x=v[i].x;
            sol[k].y=v[i].y;
            cost+=v[i].c;
        }
    }
}
bool comp(muchie a, muchie b)
{
    return a.c<b.c;
}
int main()
{
    citire ();
    combinare (i,n);
    ofstream g ("apm.out");
    sort (v+1,v+m+1,comp);
    krusk();
    g<<cost<<"\n"<<n-1<<"\n";
    for (int i=1; i<=k; i++)
    g<<sol[i].x<<" "<<sol[i].y<<"\n";
    g.close();
    return 0;
}