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

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

const int INF = INT_MAX;

struct Muchie
{
    int to, cost;
};

int main()
{
    int n, m;
    in >> n >> m;

    vector<vector<Muchie>> graph(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        in >> x >> y >> z;
        graph[x].push_back({y, z});
        graph[y].push_back({x, z});
    }

    vector<int> dist(n + 1, INF);
    vector<bool> used(n + 1, false);
    vector<int> parent(n + 1, -1);
    dist[1] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1});

    int totalCost = 0;
    vector<pair<int, int>> apmM;

    while (!pq.empty())
    {
        auto [cost, x] = pq.top();
        pq.pop();

        if (used[x]) continue;
        used[x] = true;
        totalCost += cost;

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

        for (auto &e : graph[x])
        {
            int y = e.to, z = e.cost;
            if (!used[y] && z < dist[y])
            {
                dist[y] = z;
                parent[y] = x;
                pq.push({z, y});
            }
        }
    }

    out << totalCost << "\n";
    out << n - 1 << "\n";
    for (auto &e : apmM)
        out << e.first << " " << e.second << "\n";

    return 0;
}