#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[200001], r[200001];
vector<tuple<int, int, int> > edges;
vector<pair<int, int>> tree;

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

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

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

    f.close();
}

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

    for(const auto& [cost, nodeX, nodeY] : edges) {
        if(find(nodeX) != find(nodeY)) {
            unite(find(nodeX), find(nodeY));
            tree.push_back(make_pair(nodeX, nodeY));
            treeCost += cost;
        }
    }

    g<<treeCost<<'\n';
    g<<tree.size()<<'\n';
    for(const auto& [nodeX, nodeY] : tree) {
        g<<nodeX<<" "<<nodeY<<'\n';
    }
    g.close();
}

int main() {

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