#include <fstream>
#include <utility>
#include <climits>
#include <vector>
#include <bitset>
#include <set>

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

const int nMax = 2e5;

int main () {
    int n, m; fin >> n >> m;
    std::vector<std::vector<std::pair<int, int>>> graph(
                n, std::vector<std::pair<int, int>> ());
    while (m > 0) {
        int u, v, cost; fin >> u >> v >> cost; u -= 1, v -= 1;
        graph[u].emplace_back (std::make_pair (v, cost));
        graph[v].emplace_back (std::make_pair (u, cost));
        m -= 1;
    }

    std::bitset<nMax> inTree;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> dist(n, INT_MAX); dist[0] = 0;
    std::set<std::pair<int, int>> q; q.insert ({0, 0});

    int sumMin = 0;
    while (!q.empty ()) {
        int u = q.begin ()->second;
        int cost = q.begin ()->first;
        q.erase (q.begin ());

        if (inTree[u] == false) {
            inTree[u] = true, sumMin += cost;

            for (auto x : graph[u])
                if (inTree[x.first] == false && dist[x.first] > x.second) {
                    dist[x.first] = x.second;
                    q.insert ({dist[x.first], x.first});
                    edges.emplace_back (std::make_pair (x.first, u));
                }
        }
    }

    fout << sumMin << '\n' << n - 1 << '\n';
    for (auto it : edges)
        fout << it.first + 1 << ' ' << it.second + 1 << '\n';
    return 0;
}