#include <bits/stdc++.h>
using namespace std;

const int v_len = 200001;
#define TII tuple<short, int, int>
ifstream fin("apm.in");
ofstream fout("apm.out");
int tree[v_len], treeSize[v_len];

int get_root(int node)
{
    while (tree[node] != 0)
        node = tree[node];

    return node;
}

bool join(int node1, int node2)
{
    int par1 = get_root(node1);
    int par2 = get_root(node2);

    if (par1 == par2)
        return false;

    if (treeSize[par1] >= treeSize[par2])
        treeSize[par1] += treeSize[par2], tree[par2] = par1;
    else
        treeSize[par2] += treeSize[par1], tree[par1] = par2;

    return true;
}

int main()
{
    int n, m;
    fin >> n >> m;
    vector<TII> best(m + 1);

    for (int i = 0; i < m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        best[i] = make_tuple(cost, x, y);
    }

    sort(best.begin(), best.end());

    vector<pair<int, int>> sol;
    int total = 0, nm = 0;

    for (auto curr : best)
    {
        int x = get<1>(curr), y = get<2>(curr), cost = get<0>(curr);
        if (join(x, y))
            total += cost, sol.push_back(make_pair(x, y)), nm++;

        if (nm == n - 1)
            break;
    }

    fout << total << "\n"
         << sol.size() << "\n";
    for (auto obj : sol)
        fout << obj.first << " " << obj.second << "\n";

    return 0;
}