#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

int n, m, rang[200100], pointeaza[200100], noduri, noduri_ans;
ll ans;
set<pair<int ,pair<int ,int>>> s;
vector<int> edges[200100];
bool visited[200100];

int radacina(int x) {
    int Radacina;
    for (Radacina = x; pointeaza[Radacina] != Radacina; Radacina = pointeaza[Radacina]);
    while (x != Radacina) {
        pointeaza[pointeaza[x]] = Radacina;
        x = pointeaza[x];
    }
    return Radacina;
}

void reuniune(int x, int y) {
    if (rang[x] > rang[y]) {
        pointeaza[y] = x;
    }
    else {
        pointeaza[x] = y;
    }
    if (rang[x] == rang[y]) {
        rang[y]++;
    }
}

int main() {
    fin.tie(0);
    ios::sync_with_stdio(0);
    fin >> n >> m;
    noduri = n + 1;
    for (int i = 1; i <= n; ++i) {
        rang[i] = 1;
        pointeaza[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        s.insert(make_pair(z, make_pair(x, y)));
    }
    while (!s.empty() && noduri != 0) {
        int cost = s.begin()->first;
        int node_inceput = s.begin()->second.first;
        int node_final = s.begin()->second.second;
        if (radacina(node_inceput) != radacina(node_final)) {
            ans += cost;
            noduri_ans++;
            edges[node_inceput].push_back(node_final);
            noduri--;
            reuniune(radacina(node_inceput), radacina(node_final));
        }
        s.erase(s.begin());
    }
    fout << ans << '\n' << noduri_ans << '\n';
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < edges[i].size(); ++j) {
            fout << i << " " << edges[i][j] << '\n';
        }
    }
    return 0;
}