#include <bits/stdc++.h>
using namespace std;

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

const int MAX_NUM = 2e5 + 5;

int main() {
    ios::sync_with_stdio(false);
    fin.tie(nullptr);
    int n, m;
    fin >> n >> m;
    vector<pair<int, int>> graph[n + 1];
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    vector<int> prev(n + 1, -1), cost(n + 1, INT_MAX);
    bitset<MAX_NUM> visited;
    set<pair<int, int>> s;
    int start = 1;
    cost[start] = 0;
    s.insert({0, start});
    int totalCost = 0;
    vector<pair<int, int>> answer;
    while (!s.empty()) {
        auto current = *s.begin();
        int currentNode = current.second, currentCost = current.first;
        s.erase(s.begin());
        if (!visited[currentNode]) {
            visited[currentNode] = true;
            totalCost += currentCost;
            if (prev[currentNode] != -1) {
                answer.push_back({prev[currentNode], currentNode});
            }
            for (auto [node, nodeCost] : graph[currentNode]) {
                if (!visited[node] && nodeCost < cost[node]) {
                    cost[node] = nodeCost;
                    prev[node] = currentNode;
                    s.insert({cost[node], node});
                }
            }
        }
    }
    fout << totalCost << "\n" << answer.size() << "\n";
    for (auto [a, b] : answer) {
        fout << a << " " << b << "\n";
    }
    return 0;
}