#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

struct Edge {
    int x, y, cost;

    bool operator <(const Edge& other) const {
        return cost < other.cost;
    }
};

int n, m, totalCost;
vector <int> h, t;
vector <Edge> v;
vector <pair<int, int>> ans;

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

int getRoot(int node) {
    if(node == t[node])
        return node;
    int root = getRoot(t[node]);
    t[node] = root;
    return t[node];
}

bool sameConnectedComponents(int x, int y) {
    return getRoot(x) == getRoot(y);
}

void unite(int x, int y) {
    int rootX = getRoot(x);
    int rootY = getRoot(y);
    if(rootX == rootY)
        return;
    if(h[rootX] < h[rootY])
        t[rootY] = rootX;
    else {
        t[rootX] = rootY;
        if(h[rootX] == h[rootY])
            ++h[rootY];
    }
}

void kruskal() {
    for(const auto& edge : v) {
        int x = edge.x;
        int y = edge.y;
        int cost = edge.cost;
        if(sameConnectedComponents(x, y))
            continue;
        unite(x, y);
        totalCost += cost;
        ans.push_back({x, y});
    }
}

void read() {
    fin >> n >> m;
    init();
    int x, y, cost;
    for(int i = 1; i <= m; i ++) {
        fin >> x >> y >> cost;
        v.push_back({x, y, cost});
    }
    sort(v.begin(), v.end());
}

void print() {
    fout << totalCost << '\n' << ans.size() << '\n';
    for(const auto& pair : ans)
        fout << pair.first << " " << pair.second << '\n';
}

int main() {
    read();
    kruskal();
    print();
}