#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

# define N 200009
# define M 400009

void proces();

int n,m,sum;
int v[N];
int s[N][2];

struct nod {
    int cost,x,y;
};
nod r[M];

int tata(int x)
{
    if(v[x] == 0){
        return x;
    }
    int h = tata(v[x]);
    v[x] = h;
    return h;

}
bool maxim(nod a, nod b)
{
    return(a.cost < b.cost);
}
void citire()
{
    int c,a,b;
    f>>n>>m;
    for( int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        r[i].cost = c;
        r[i].x = a;
        r[i].y = b;
    }
    sort(r+1,r+m+1,maxim);
    proces();
}
void proces()
{
    int p=0,a,b;
    for( int i=1;i<=m;i++)
    {
        a = tata(r[i].x);
        b = tata (r[i].y);
        if(a==b)
            continue;
        v[b] = a;
        sum += r[i].cost;
        s[p][0] = r[i].x;
        s[p][1] = r[i].y;
        p++;
        if(p == n-1)
        {
            break;
        }
    }
    g<<sum<<'\n';
    g<<p<<'\n';
    for( int i=0;i<n-1;i++)
    {
        g<<s[i][1]<<" "<<s[i][0]<<'\n';
    }
}
int main()
{
    citire();
    return 0;
}