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

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

const int MAXN = 2e5;
int root[MAXN + 1], depth[MAXN + 1];
int N, M;

int getRoot(int node)
{
    if (root[node] == node)
        return node;
    return (root[node] = getRoot(root[node]));
}

bool unite(int x, int y)
{
    int rootX = getRoot(x), rootY = getRoot(y);
    if (rootX == rootY)
        return false;
    if (depth[rootX] < depth[rootY])
    {
        root[rootX] = rootY;
    }
    else
    {
        root[rootY] = rootX;
        if (depth[rootX] == depth[rootY])
            ++depth[rootX];
    }
    return true;
}

vector<tuple<int, int, int>> edges;
vector<pair<int, int>> sol;

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
        root[i] = i;
    int a, b, c;
    while (M--)
    {
        fin >> a >> b >> c;
        edges.emplace_back(c, a, b);
    }
    sort(edges.begin(), edges.end(), less<tuple<int, int, int>>());
    int total_cost = 0, edges_added = 0;
    for (const auto &edge : edges)
    {
        tie(c, a, b) = edge;
        if (unite(a, b))
        {
            sol.emplace_back(a, b);
            total_cost += c;
            if (++edges_added == N - 1)
                break;
        }
    }
    fout << total_cost << '\n'
         << N - 1 << '\n';
    for (const auto &ans : sol)
    {
        fout << ans.first << ' ' << ans.second << '\n';
    }
    return 0;
}