#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXN 200010
#define MAXM 400010

using namespace std;

struct edge{
    int x, y, cost;
}edges[MAXM], solution[MAXN];

int height[MAXN], father[MAXN], n, m, solCost = 0;

void readInput() {
    ifstream fin("apm.in");
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> edges[i].x >> edges[i].y >> edges[i].cost;
    }
}

bool cmp(edge a, edge b) {
    if (a.cost != b.cost)
        return (a.cost < b.cost);
    else if (a.x != b.x)
        return (a.x < b.x);
    return (a.y < b.y);
}

int doFather(int node) {
    int f;
    for (f = node; father[f] != f; f = father[f]) {}
    for (; node != f; node = father[f])
        father[node] = f;
    return f;
}

void reunite(int x, int y) {
    if (height[x] > height[y]) {
        height[y] = height[x];
        father[y] = doFather[x];
    }
    else if (height[x] == height[y]) {
        height[x]++;
        height[y] = height[x];
        father[x] = doFather[y];
    }
    else {
        height[x] = height[y];
        father[x] = doFather[y];
    }
}

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

void createTree() {
    int k = 0;
    for (int i = 0; i < m; i++) {
        if (doFather(edges[i].x) != doFather(edges[i].y)) {
            reunite(edges[i].x, edges[i].y);
            solCost += edges[i].cost;
            solution[k++] = edges[i];
        }
    }
}

void printSolution() {
    ofstream fout("apm.out");
    fout << solCost << "\n" << n - 1 << "\n";
    for (int i = 0; i < n - 1; i++)
        fout << solution[i].x << " " << solution[i].y << "\n";
}

int main() {
    readInput();
    sort(edges, edges + m, cmp);
    initialize();
    createTree();
    printSolution();
    return 0;
}