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

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

int N, M;
int t[Nmax], h[Nmax];
struct edge{
   int x, y, c;
};
edge v[Nmax];

bool cmp(edge a, edge b) {
   return a.c < b.c;
}


int root(int x) {
   if (!t[x]) return x;
   return root(t[x]);
}
void unite(int x, int y) {
    if (h[x] < h[y]) swap(x, y);
    if (h[x] == h[y]) ++h[x];
    t[y] = x;
}
int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        v[i] = {x, y, c};
    }
    sort(v + 1, v + M + 1, cmp);

    int ans = 0;
    vector<pair<int, int> > apm;
    for (int i = 1; i <= M; ++i) {
        int x = root(v[i].x), y = root(v[i].y);
        if (x == y) continue;
        unite(x, y);
        ans += v[i].c;
        apm.push_back(make_pair(v[i].x, v[i].y));
    }

    fout << ans << '\n' << N - 1 << '\n';
    for (auto it: apm)
        fout << it.first << " " << it.second << '\n';

    return 0;
}