#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m;
int t[200005], r[200005];
vector<tuple<int, int, int>> edges;
vector<pair<int, int>> result;

void init() {
    for(int i = 1;i <= n;++i) {
        t[i] = i;
        r[i] = 1;
    }
}

void unite(const int& x, const int& y) {
    if(r[x] > r[y]) {
        r[x] += r[y];
        t[y] = x;
        return;
    }

    r[y] += r[x];
    t[x] = y;
}

int find(const int& x) {
    if(t[x] == x) {
        return x;
    }
    return t[x] = find(t[x]);
}

void read() {
    f>>n>>m;
    init();
    int x, y, z;
    for(int i = 1;i <= m;++i) {
        f>>x>>y>>z;
        edges.push_back({z, x, y});
    }
}

void solve() {
    int total_cost = 0;
    sort(edges.begin(), edges.end());

    for(const auto& edge : edges) {
        int cost = get<0>(edge), v1 = get<1>(edge), v2 = get<2>(edge);
        if(find(v1) != find(v2)) {
            unite(find(v1), find(v2));
            total_cost += cost;
            result.push_back(make_pair(v1, v2));
        }
    }

    g<<total_cost<<'\n'<<result.size()<<'\n';
    for(const auto& [v1, v2] : result) {
        g<<v1<<" "<<v2<<'\n';
    }
}

int main() {

    read();
    solve();
    return 0;
}