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

using namespace std;

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

int vector_t[200003], rang[200003];
pair <int, int>pereche[200003];
int n, m;

struct muchie{
    int x, y, cost;
}v[400003];

void citire()
{
    f >> n >> m;
    for(int i = 1; i <= m; i++)
        f >> v[i].x >> v[i].y >> v[i].cost;
}
int cauta(int x)
{
    //cat timp nodul e diferit de tatal sau, urc in arbore
    while(vector_t[x] != x)
        x = vector_t[x];
    return x;
}
bool compara(muchie a, muchie b)
{
    return (a.cost < b.cost);
}
void uneste(int a, int b)
{
    if(rang[a] < rang[b])
        vector_t[a] = b;
    if(rang[b]  < rang[a])
        vector_t[b] = a;
    if(rang[a] ==  rang[b])
    {
        vector_t[a] = b;
        //cresc rangul lui b daca sunt ambele egale
        rang[b]++;
    }
}
int main()
{
    int suma = 0;
    int k = 0;
    citire();
    //sortez crescator in functie de cost
    sort(v+1, v+m+1, compara);
    //initializez vectorul de tati, fiecare nod va fi egal cu tatal sau
    for(int i = 1; i <= n; i++)
    {
        vector_t[i] = i;
        //marchez ca rangul fiecarui nod sa fie 1
        rang[i] = 1;
    }
    for(int i = 1; i <= m; i++)
    {
        int muchie_a;
        int muchie_b;

        muchie_a = cauta(v[i].x);
        muchie_b = cauta(v[i].y);
//daca radacinile celor 2 noduri sunt diferite
        if(muchie_a != muchie_b)
        {
            k++;
            uneste(muchie_a, muchie_b);
            pereche[k].first = v[i].x;
            pereche[k].second = v[i].y;
            suma = suma + v[i].cost;
        }
    }
    g << suma << '\n';
    g << n - 1;
    g << '\n';
    for(int i = 1; i < n; i++)
        g << pereche[i].second << " "<<pereche[i].first << '\n';

}