#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int main()
{
    ios_base::sync_with_stdio(false);
    f.tie(NULL);

    int n, m;
    f >> n >> m;
    vector<vector<pair<int, int>>> graph(n, vector<pair<int, int>>());

    for (int i = 0; i < m; i++)
    {
        int x, y, w;
        f >> x >> y >> w;
        x--;
        y--;
        graph[x].push_back({y, w});
        graph[y].push_back({x, w});
    }

    auto Prim = [&](int node, int &mst_cost) -> vector<pair<int, int>>
    {
        const int NMAX = 200005;
        const int INF = 0x3F3F3F3F;
        int edge_cost;
        bitset<NMAX> used;
        vector<int> dist(n, INF), parent(n);
        vector<pair<int, int>> mst_edges;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        dist[node] = 0;
        pq.push({0, node});

        while (!pq.empty())
        {
            edge_cost = pq.top().first;
            node = pq.top().second;
            pq.pop();

            if (!used[node])
            {
                if (node)
                {
                    mst_cost += edge_cost;
                    mst_edges.push_back({node, parent[node]});
                }

                for (auto &[neighbour, cost] : graph[node])
                    if (!used[neighbour] && cost < dist[neighbour])
                    {
                        dist[neighbour] = cost;
                        parent[neighbour] = node;
                        pq.push({dist[neighbour], neighbour});
                    }
                used[node] = 1;
            }
        }
        return mst_edges;
    };

    int mst_cost = 0;
    vector<pair<int, int>> mst_edges = Prim(0, mst_cost);

    g << mst_cost << '\n';
    g << n - 1 << '\n';
    for (auto &[x, y] : mst_edges)
        g << x + 1 << ' ' << y + 1 << '\n';
    return 0;
}