#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

const int N_MAX = 200000;
const int M_MAX = 400000;
ifstream ka("apm.in");
ofstream ki("apm.out");

struct muchie
{
    int a, b, cost;
}muchii[M_MAX + 1], sol[N_MAX + 1];

bool comp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int n, m, minim = 0x7fffffff;

int rad[N_MAX + 1];
int pe_drum[N_MAX + 1];

int cost;

int rada(int t)
{
    pe_drum[0] = 0;
    while(rad[t] != t)
    {
        pe_drum[++pe_drum[0]] = t;
        t = rad[t];
    }
    for(int i = 1; i <= pe_drum[0]; i++)
        rad[pe_drum[i]] = t;
    return t;
}

int main()
{
    ka >> n >> m;
    for(int i = 1; i <= n; i++)
        rad[i] = i;
    for(int i = 1; i <= m; i++)
    {
        muchie mm;
        ka >> mm.a >> mm.b >> mm.cost;
        muchii[++muchii[0].a] = mm;
    }
    sort(muchii + 1, muchii + muchii[0].a + 1, comp);
    for(int i = 1; i <= muchii[0].a; i++)
    {
        if(rada(muchii[i].a) != rada(muchii[i].b))
        {
            rad[rada(muchii[i].b)] = rada(muchii[i].a);
            cost += muchii[i].cost;
            sol[++sol[0].a] = muchii[i];
        }
    }
    ki << cost << '\n' << sol[0].a << '\n';
    for(int i = 1; i <= sol[0].a; i++)
        ki << sol[i].b << " " << sol[i].a << '\n';
}