#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define maxN 200005

using namespace std;

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

struct Edge {
    pair <int, int> vert;
    int cost;
    Edge (pair<int, int> v, int c) : vert(v), cost(c) {};
};

vector <Edge> G;
int n, m, tata[maxN], rang[maxN];

bool cmp (Edge a, Edge b) {
    return a.cost < b.cost;
}

void make_set (int nod) {
    rang[nod] = 0;
    tata[nod] = nod;
}

int find (int nod) {
    if (tata[nod] != nod) {
        return find(tata[nod]);
    }
    return nod;
}

int unesc (int root1, int root2) {
    if (rang[root1] > rang[root2]) {
        tata[root2] = root1;
    }
    else {
        if (rang[root1] < rang[root2]) {
            tata[root1] = root2;
        }
        else {
            tata[root1] = root2;
            rang[root2]++;
        }
    }
}

void Kruskal () {
    int root1, root2, sum = 0, s = 0;
    vector <Edge> arb;
    for (int i = 1; i <= n; ++i) {
        make_set(i);
    }
    sort(G.begin(), G.end(), cmp);
    for (int i = 0; i < m; ++i) {
        root1 = find(G[i].vert.first);
        root2 = find(G[i].vert.second);
        if (root1 != root2) {
            arb.push_back(G[i]);
            unesc(root1, root2);
            sum+= G[i].cost;
            s++;
        }
    }
    fout << sum << '\n';
    fout << s << '\n';
    for (int i = 0; i < s; ++i) {
        fout << arb[i].vert.first << " " << arb[i].vert.second << '\n';
    }
}

int main () {
    fin >> n >> m;
    int x, y, w;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> w;
        G.push_back(Edge({y, x}, w));
    }
    Kruskal();
}