#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NM 400010
using namespace std;

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

int c[NM], x[NM], y[NM], gr[NM], ind[NM];
int n, m, cost;
vector < int > sol;

bool cmp(int a, int b)
{
    return c[a] < c[b];
}

int grupa(int i)
{
    if (gr[i] == i) return i;
    gr[i] = grupa(gr[i]);
    return gr[i];
}

void U(int i,int j)
{
    gr[grupa(i)] = grupa(j);
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> x[i] >> y[i] >> c[i];
        ind[i] = i;
    }
    for(int i = 1; i <= n; ++i) gr[i] = i;
    sort(ind + 1, ind + m + 1, cmp);
    for(int i = 1; i <= m; ++i)
    {
        if(grupa( x[ ind[ i ] ] ) != grupa( y[ ind[ i ] ] ))
        {
            cost += c[ ind [ i ] ];
            U(x[ ind[ i ]], y[ ind[ i ] ]);
            sol.push_back(ind[i]);
        }
    }
    g << cost << '\n' << n - 1 << '\n';
    for(int i = 0; i < n - 1; ++i)
        g << x[sol[i]] << ' ' << y[sol[i]] << '\n';
}