//Algoritmul Krusksal
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAXM 400000
#define MAXN 200001
using namespace std;

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

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

int n, m, nr, traseu[MAXN], rang[MAXN], sol[MAXN], k;
long long suma;

void read()
{
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }
}

bool cmp(muchie a, muchie b)
{
    if (a.cost < b.cost)
        return true;
    return false;
}

void init()
{
    for (int i = 1; i <= n; ++i)
        traseu[i] = rang[i] = i;
}

int Find(int x)
{
    if (traseu[x] == x)
        return x;
    traseu[x] = Find(traseu[x]);
    return traseu[x];
}

void Unite(int x, int y)
{
    x = Find(x);
    y = Find(y);

    if (rang[x] > rang[y])
        swap(x, y);
    traseu[x] = y;
    rang[y] += rang[x];
}

void solve()
{
    int a, b, aux, grupa_a, grupa_b;

    while (nr < n - 1) {
        a = v[k].x;
        b = v[k].y;
        grupa_a = Find(a);
        grupa_b = Find(b);
        if (grupa_a != grupa_b) {
            sol[nr++] = k;
            suma += v[k].cost;
            Unite(grupa_a, grupa_b);
            /*
            cout << a << ' ' << b << '\n';
            for (int i = 1; i <= n; ++i)
                cout << viz[i] << ' ';
            cout << "\n\n";
            */
        }
        k++;
    }
}

void write()
{
    int aux;

    fout << suma << '\n' << n - 1 << '\n';
    for (int i = 0; i <= n - 2; ++i) {
        aux = sol[i];
        fout << v[aux].x << ' ' << v[aux].y << '\n';
    }
}

int main()
{
    read();
    init();
    sort(v, v + m, cmp);
    solve();
    write();
    return 0;
}