#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n, m, dsu[200009], sz[200009], tot;
struct edge
{
    int x, y, cst;
};
vector<edge> v;
int find(int);
vector<pair<int, int>> rez;
void unify(int, int);
int main()
{
    f >> n >> m;
    for (int i = 1; i <= n; i++)
        dsu[i] = i;
    v.resize(m);
    for (edge &i : v)
        f >> i.x >> i.y >> i.cst;
    sort(v.begin(), v.end(), [](const edge &a, const edge &b) { return a.cst < b.cst; });
    for (int i = 0, t = n; i < m && t != 1; i++)
    {
        int x = v[i].x, y = v[i].y;
        x = find(x);
        y = find(y);
        if (x == y)
            continue;
        t--;
        unify(x, y);
        tot += v[i].cst;
        rez.push_back({v[i].x, v[i].y});
    }
    g << tot << '\n'
      << rez.size() << '\n';
    for (const auto &i : rez)
        g << i.first << " " << i.second << '\n';
    return 0;
}
int find(int x)
{
    if (x == dsu[x])
        return x;
    return dsu[x] = find(dsu[x]);
}
void unify(int x, int y)
{
    if (sz[x] > sz[y])
        swap(x, y);
    sz[y] += sz[x];
    dsu[x] = dsu[y];
}