#include <bits/stdc++.h>

using namespace std;

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

const int maxn = 2e5 + 5;

struct edge {
    int from, to, weight;
    bool operator < (const edge &t) const {
        return weight < t.weight;
    }
    bool operator > (const edge &t) const {
        return weight > t.weight;
    }
};

priority_queue<edge, vector<edge>, greater<edge> > heap;
int t[maxn], h[maxn], n, m, cost;
vector<pair<int,int>> sol;

int Find(int x) {
    int r = x;
    while(t[r]) {
        r = t[r];
    }
    while(t[x]) {
        int y = t[x];
        t[x] = r;
        x = y;
    }
    return r;
}

void Union(int x, int y) {
    if(h[x] > h[y]) {
        t[y] = x;
    }
    else {
        t[x] = y;
        if(h[x] == h[y]) ++h[y];
    }
}

int main() {
    fin >> n >> m;

    while(m--) {
        edge c;
        fin >> c.from >> c.to >> c.weight;
        heap.push(c);
    }

    while(sol.size() < n - 1) {
        edge c = heap.top();
        int x = Find(c.from);
        int y = Find(c.to);
        heap.pop();
        if(x != y) {
            Union(x, y);
            sol.emplace_back(c.from, c.to);
            cost += c.weight;
        }
    }

    fout << cost << "\n" << sol.size() << "\n";
    for(auto k : sol)
        fout << k.first << " " << k.second << "\n";

    return 0;
}