#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, cost;
};


int find(int u, vector<int>& parent) {
    if (parent[u] != u)
        parent[u] = find(parent[u], parent); 
    return parent[u];
}

void unite(int u, int v, vector<int>& parent, vector<int>& rank) {
    int rootU = find(u, parent);
    int rootV = find(v, parent);
    if (rootU != rootV) {
        if (rank[rootU] < rank[rootV])
            parent[rootU] = rootV;
        else if (rank[rootU] > rank[rootV])
            parent[rootV] = rootU;
        else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

bool sameComponent(int u, int v, vector<int>& parent) {
    return find(u, parent) == find(v, parent);
}

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

    int N, M;
    fin >> N >> M;

    vector<Edge> edges(M);
    for (int i = 0; i < M; i++) {
        fin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }

  
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.cost < b.cost;
    });

    vector<int> parent(N + 1);
    vector<int> rank(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        parent[i] = i; 
    }

    vector<Edge> mst; 
    int totalCost = 0;

    for (Edge& edge : edges) {
        if (!sameComponent(edge.u, edge.v, parent)) {
            unite(edge.u, edge.v, parent, rank);
            mst.push_back(edge);
            totalCost += edge.cost;
            if (mst.size() == N - 1) 
                break;
        }
    }


    fout << totalCost << endl;
    fout << mst.size() << endl;
    for (Edge& edge : mst) {
        fout << edge.v << " " << edge.u << endl;
    }

    return 0;
}