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

int main() {

    ifstream fin("apm.in");
    ofstream fout("apmout.txt");

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

    vector<vector<pair<int, int>>> adj(N + 1);

    for (int i = 0; i < M; i++) {
        int u, v, c;
        fin >> u >> v >> c;
        adj[u].push_back({ v, c });
        adj[v].push_back({ u, c });
    }

    priority_queue<pair<int, int>,vector<pair<int, int>>,greater<pair<int, int>>> pq;

    vector<bool> visited(N + 1, false);
    vector<int> parent(N + 1, -1);
    vector<pair<int, int>> mstEdges;
    long long totalCost = 0;

    pq.push({ 0, 1 }); 

    while (!pq.empty()) {
        auto p = pq.top(); pq.pop();
        int cost = p.first;
        int node = p.second;

        if (visited[node]) continue;

        visited[node] = true;
        totalCost += cost;

        if (parent[node] != -1)
            mstEdges.push_back({ parent[node], node });

        for (auto v : adj[node]) {
            int nextNode = v.first;
            int edgeCost = v.second;

            if (!visited[nextNode]) {
                pq.push({ edgeCost, nextNode });
                parent[nextNode] = node;
            }
        }
    }

    fout << totalCost << endl;
    fout << mstEdges.size() << endl;
    for (auto& e : mstEdges)
        fout << e.first << " " << e.second << endl;

    fin.close();
    fout.close();

    return 0;
}