#include <cstdio>
#include <ctime>

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

ifstream fin("apm.in");
ofstream fout("apm.out");
const int MAX_N = 200100;
const int MAX_M = 400100;

int N, M;
struct Edge {
    int node1, node2, cost;
    bool operator< (const Edge& other) const {
        return cost < other.cost;
    }
} edges[MAX_M];
int father[MAX_N];

int solCost;
vector<int> solEdges;

void read_input(), solve(), print_output();

void build_sets();
void unite_sets(int node1, int node2);
int get_root(int node);
bool same_set(int node1, int node2);

int main() {
    read_input();
    solve();
    print_output();
    return 0;
}

void read_input() {
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        fin >> edges[i].node1 >> edges[i].node2 >> edges[i].cost;
    }
}

void solve() {
    srand(time(NULL));
    build_sets();
    sort(edges + 1, edges + M + 1);
    for (int i = 1; i <= M; ++i) {
        if (!same_set(edges[i].node1, edges[i].node2)) {
            unite_sets(edges[i].node1, edges[i].node2);
            solCost += edges[i].cost;
            solEdges.push_back(i);
        }
    }
}

void print_output() {
    fout << solCost << '\n';
    fout << solEdges.size() << '\n';
    for (unsigned int i = 0; i < solEdges.size(); i++) {
        fout << edges[solEdges[i]].node1 << ' ' << edges[solEdges[i]].node2 << '\n';
    }
}

void build_sets() {
    for (int i = 1; i <= N; i++) {
        father[i] = i;
    }
}

void unite_sets(int node1, int node2) {
    int root1 = get_root(node1);
    int root2 = get_root(node2);
    if (root1 == root2) return;

    if (rand() & 1) {
        father[root1] = root2;
    } else {
        father[root2] = root1;
    }
}

int get_root(int node) {
    if (father[node] == node) {
        return node;
    }
    return father[node] = get_root(father[node]);
}

bool same_set(int node1, int node2) {
    return get_root(node1) == get_root(node2);
}