//ex 1
#include <bits/stdc++.h>
using namespace std;
int par[200005], sz[200005];
int find(int x) {
while (par[x] != x) {
par[x] = par[par[x]];
x = par[x];
}
return x;
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
return true;
}
struct Edge {
int x, y, c;
};
int main() {
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m;
fin >> n >> m;
vector<Edge> e(m);
for (auto &ed : e) fin >> ed.x >> ed.y >> ed.c;
sort(e.begin(), e.end(), [](const Edge &a, const Edge &b) {
return a.c < b.c;
});
for (int i = 1; i <= n; i++) {
par[i] = i;
sz[i] = 1;
}
long long total = 0;
vector<pair<int, int>> chosen;
chosen.reserve(n);
for (const auto &ed : e) {
if (unite(ed.x, ed.y)) {
total += ed.c;
chosen.push_back({ed.x, ed.y});
if ((int)chosen.size() == n - 1) break;
}
}
fout << total << "\n" << chosen.size() << "\n";
for (auto &p : chosen) fout << p.first << " " << p.second << "\n";
return 0;
}