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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int n, m;
struct muchie{
    int x, y, cost;
}v[20003];
int vector_t[20003], rang[20003];
pair <int, int>pereche[20003];
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)
{
    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;
        rang[b]++;
    }
}
int main()
{
    int suma = 0;
    int k = 0;
    citire();
    sort(v+1, v+m+1, compara);
    for(int i = 1; i <= n; i++)
    {
        vector_t[i] = i;
        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);

        if(muchie_a != muchie_b)
        {
            uneste(muchie_a, muchie_b);
            pereche[++k].first = v[i].x;
            pereche[k].second = v[i].y;
            suma = suma + v[i].cost;
        }
    }
    g << suma << endl;
    g << n - 1;
    g << endl;
    for(int i = 1; i < n; i++)
        g << pereche[i].second << " "<<pereche[i].first << endl;

}