#include <bits/stdc++.h>

using namespace std;

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

struct muchie {
    int a, b, cost;
} v[400005];

vector <muchie> V;

int par[400005];

int parinte(int i)
{
    if (par[i] == i) return i;
    par[i] = parinte(par[i]);
    return par[i];
}

void reuniune(int i, int j)
{
    par[parinte(j)] = parinte(i);
}

bool cmp (muchie a, muchie b)
{
    return a.cost < b.cost;
}

int main()
{
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        fin >> v[i].a >> v[i].b >> v[i].cost;
    }
    sort(v + 1, v + m + 1, cmp);
//    for (int i = 1; i <= m; i ++) {
//        fout << v[i].a << " " << v[i].b << " " << v[i].cost << "\n";
//    }
    for (int i = 1; i <= n; i ++) {
        par[i] = i;
    }
    int costTotal = 0;
    for (int i = 1; i <= m; i ++) {
        if (parinte(v[i].a) != parinte(v[i].b)) {
            reuniune(v[i].a, v[i].b);
            V.push_back(v[i]);
            costTotal += v[i].cost;
        }
    }
    int N = V.size();
    fout << costTotal << "\n" << N << "\n";
    for (int i = 0; i < N; i ++) fout << V[i].a << " " << V[i].b << "\n";
    return 0;
}