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

const int NMAX = 200000;
const int MMAX = 400000;
int N, M;

struct Edge {
    int x, y;
    int cost;
} E[MMAX + 1];

void readInput() {
    ifstream f("apm.in");

    f >> N >> M;
    for (int i = 1; i <= M; i++) {
        f >> E[i].x >> E[i].y >> E[i].cost;
    }
    f.close();
}

class DSU {
    vector<int> reprez, rank;
public:
    DSU(int N) {
        reprez = vector<int>(N + 1);
        rank = vector<int>(N + 1, 1);
        for (int i = 1; i <= N; i++)
            reprez[i] = i;
    }

    int find(int i) {
        // gasesc reprezentantul unui cluster
        if (i == reprez[i])
            return i;
        return reprez[i] = find(reprez[i]);
    }

    void unite(int u, int v) {
        // daca graful ramane un arbore, pot da join la cele 2 clustere
        int U = find(u), V = find(v);

        if (U != V) {
            // ramane arbore
            if (rank[U] > rank[V]) {
                reprez[V] = U;
            }
            else if (rank[U] < rank[V]) {
                reprez[U] = V;
            }
            else {
                reprez[U] = V;
                rank[V] ++;
            }
        }
    }
};

vector<Edge> solution;
int costMST = 0;

void kruskal() {
    DSU dsu(N); // initialize mst

    sort(E + 1, E + M + 1, [](Edge a, Edge b){
        if (a.cost < b.cost)
            return true;
        return false;    
    }); // sort edges ascending

    for (int i = 1; i <= M; i++) {
        if (dsu.find(E[i].x) != dsu.find(E[i].y)) {
            solution.push_back(E[i]);
            dsu.unite(E[i].x, E[i].y);
            costMST += E[i].cost;
        }
    }
}

void output() {
    ofstream g("apm.out");

    g << costMST << endl;
    g << solution.size() << endl;
    for (auto edge : solution) {
        g << edge.x << " " << edge.y << endl;
    }

    g.close();
}

int main() {
    readInput();
    kruskal();
    output();
    return 0;
}