#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX = 2e5 + 1;
int n, m, ans = 0, parent[NMAX], h[NMAX];
vector<tuple<int, int, int>> edges;
vector<pair<int, int>> tree;

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

void Union(int x, int y)
{
    x = Find(x), y = Find(y);
    if(x == y)
        return;
    if(h[x] < h[y])
        parent[x] = y;
    else if(h[x] > h[y])
        parent[y] = x;
    else
        parent[x] = y, h[y]++;
}

int main()
{
    fin >> n >> m;
    iota(parent + 1, parent + n + 1, 1);
    while(m--)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        edges.push_back({cost, x, y});
    }
    sort(edges.begin(), edges.end());
    for(auto [cost, x, y] : edges)
    {
        if(Find(x) != Find(y))
        {
            ans += cost;
            tree.push_back({x, y});
            Union(x, y);
        }
    }
    fout << ans << "\n" << tree.size() << "\n";
    for(auto [x, y] : tree)
        fout << x << " " << y << "\n";

    return 0;
}