#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm> // for sort

using namespace std;

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

int find(vector<int>& parent, int i) {
    // daca parintele nu este 
    if(parent[i] != i)
        parent[i] = find(parent, parent[i]);
    return parent[i];
}

void Union(vector<int>& parent, vector<int>& rank, int x, int y) {
    // cautam parintii lui x si y
    int xroot = find(parent, x);
    int yroot = find(parent, y);

    // componenta mai mica se alatura componentei mai mari
    if (rank[xroot] < rank[yroot])
        parent[xroot] = yroot;
    else if (rank[xroot] > rank[yroot])
        parent[yroot] = xroot;
    // daca au aceeasi adancime nu este relevant felul in care
    // se alatura, iar adancimea va creste
    else {
        parent[yroot] = xroot;
        rank[xroot]++;
    }
}

void kruskal (vector<vector<int>> edgeList, int n) {
    
    // Sortare dupa cost
    sort(edgeList.begin(), edgeList.end());

    for (const vector<int>& edge : edgeList) {
        for (int value : edge) {
            cout << value << " ";
        }
        cout << endl;
    }

    // Initializare parinte si reprezentant (rank)
    vector<int> parent(n + 1);
    vector<int> rank(n + 1, 0);
    // cost MST
    int total_cost = 0;
    // numar total muchii
    int no_edges = 0;

    // Initializare parinte
    for (int i = 1; i < n + 1; i++) {
        parent[i] = i;
    }

    // Initializare rezultat
    vector<vector<int>> resulted_mst;

    // Parcurgem toate muchiile deja sortate dupa cost
    for (const auto& edge : edgeList) {
        // gasim parintele primului varf
        int x = find(parent, edge[1]);
        // gasim parintele celui de-al doilea varf
        int y = find(parent, edge[2]);

        // daca parintii sunt diferiti 
        // (adica nu fac parte din aceeasi componenta conexa/acelasi grup)
        if (x != y) {
            // se adauga muchia in MST
            resulted_mst.push_back({edge[1], edge[2], edge[0]});
            total_cost += edge[0];
            no_edges += 1;
            // si creeam o singura componenta conexa
            Union(parent, rank, x, y);
        }
    }
    fout << total_cost << endl;
    fout << no_edges << endl;

    for (const auto& edge : resulted_mst) {
        fout << edge[0] << " " <<  edge[1] << endl;
    }
}

int main() {
    int N, M;
    fin >> N >> M;

    vector<vector<int>> edgeList;

    for (int i = 0; i < M; i++) {
        int X, Y, C;
        fin >> X >> Y >> C;
        edgeList.push_back({C, X, Y});
    }
    kruskal(edgeList, N);

    return 0;
}