#include    <fstream>
#include    <algorithm>
#include     <iostream>
#define dim 450000
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");


struct graf {

    int x, y, c;
}g[dim];

int t[dim];
graf rez[dim];
int n, m;

bool compara(graf a, graf b)
{
    if (a.c < b.c) return 1;
    return 0;
}

void citire()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, d;
        fin >> a >> b >> d;
        g[i].x = a;
        g[i].y = b;
        g[i].c = d;
    }
}

int radacina(int val)
{
    if (t[val] == val) return val;
    else return radacina(t[val]);
}

void legatura(int a, int b)
{
    t[a] = t[b];
}

void rezolvare()
{
    int cnt = 0;
    int cost = 0;
    sort(g + 1, g + 1 + m, compara);
    for (int i = 1; i <= n; i++) t[i] = i;
    //cout << g[1].x << ' ' << g[1].y << ' ';
    for (int i = 1; i <= m && cnt < n; i++)
    {
        int a = radacina(g[i].x);
        int b = radacina(g[i].y);
        // cout << a << ' ' << b << '\n';
        if (a != b)
        {
            cost += g[i].c;
            rez[++cnt] = g[i];
            legatura(a, b);
        }
    }
    fout << cost << '\n';
    fout << n - 1 << '\n';
    for (int i = 1; i < n; i++)
        fout << rez[i].x << ' ' << rez[i].y << '\n';

}

int main()
{
    citire();
    rezolvare();
}