#include <iostream>
#include <fstream>
#include <algorithm>
#define nmax 200005
using namespace std;

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

struct GRAF {
    int x, y, cost;
} G[nmax];
struct sol {
    int x, y;
} S[nmax];
int n, m, nrMuchii, COST;
int R[nmax], NR[nmax];

void readData() {
    int i;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
        fin >> G[i].x >> G[i].y >> G[i].cost;
}

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

void initialize() {
    int i;
    for (i = 1; i <= n; i++) {
        R[i] = i;
        NR[i] = 1;
    }
}

int root(int x) {
    if (R[x] == x)
        return x;
    return root(R[x]);
}

void solve() {
    int i;
    sort(G+1, G+m+1, cmp);
    initialize();
    for (i = 1; i <= m; i++) {
        int n1 = root(G[i].x);
        int n2 = root(G[i].y);
        if (n1 == n2)
            continue;
        if (NR[n1] >= NR[n2]) {
            NR[n1] += NR[n2];
            R[n2] = n1;
        } else {
            NR[n2] += NR[n1];
            R[n1] = n2;
        }
        COST += G[i].cost;
        nrMuchii++;
        S[nrMuchii].x = G[i].x;
        S[nrMuchii].y = G[i].y;
    }
}

void writeData() {
    int i;
    fout << COST << "\n";
    fout << nrMuchii << "\n";
    for (i = 1; i <= nrMuchii; i++)
        fout << S[i].y << " " << S[i].x << "\n";
}

int main() {
    readData();
    solve();
    writeData();
    fin.close();
    fout.close();
    return 0;
}