#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 200001;
const int MMAX = 400001;
int n, m, tree[NMAX], k;
long long c;

struct edge
{
    int x, y, cost;
} v[MMAX], a[NMAX];

bool compare_cost(edge a, edge b)
{
    return a.cost < b.cost;
}

int find_root(int node)
{
    if (tree[node] == node)
        return node;
    return tree[node] = find_root(tree[node]);
}

void Kruskal()
{
    int root_x, root_y;
    for (int i = 1; i <= n; i++)
        tree[i] = i;

    for (int i = 1; i <= m && k < n - 1; i++)
    {
        root_x = find_root(v[i].x);
        root_y = find_root(v[i].y);

        if (root_x != root_y)
        {
            c = c + v[i].cost;
            a[++k] = v[i];
            tree[root_x] = root_y;
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;

    sort(v + 1, v + m + 1, compare_cost);

    Kruskal();

    fout << c << '\n';
    fout << k << '\n';
    for (int i = 1; i <= k; i++)
        fout << a[i].x << " " << a[i].y << '\n';

    return 0;
}