#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 tata[nmax],m,k,cost;
bool comp(muchie a, muchie b)
{
    return a.c<b.c;
}
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);
                }
        }
}
void minheap ()
{
    for (i=n/2;i>=1;i--)
        combinare(i,n);
}
int radacina(int nod)
{
    if (tata[nod]==0)
        return nod;
    else {
        tata[nod]=radacina(tata[nod]);
        return tata[nod];
    }
}
void citire ()
{
    ifstream f ("apm.in");
    f>>n>>m;
    while (f>>v[i].x>>v[i].y>>v[i].c) i++;
    f.close ();
}
void solve() {
    int i,tx,ty;
    for (i=1; i<=m; i++)
    {
        tx=radacina(v[i].x);
        ty=radacina(v[i].y);
        if (tx!=ty) {
            tata[tx]=ty;
            k++;
            sol[k].x=v[i].x;
            sol[k].y=v[i].y;
            cost+=v[i].c;
        }
    }
}
int main()
{
    citire ();
    minheap();
    ofstream g ("apm.out");
    sort (v+1,v+m+1,comp);
    solve();
    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;
}