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

struct cmp
{
    bool operator()(const pair<int, pair<int, int>> &a,
                    const pair<int, pair<int, int>> &b)
    {
        return a.first > b.first;
    }
};

int main()
{
    int N, M, i, X, Y, C;
    ifstream f("apm.in");
    f >> N >> M;
    vector<pair<int, int>> adjList[N + 1];
    for (i = 0; i < M; i++)
    {
        f >> X >> Y >> C;
        adjList[X].push_back({Y, C});
        adjList[Y].push_back({X, C});
    }
    f.close();

    int father[N + 1];
    for (i = 1; i <= N; i++)
        father[i] = 0;
    priority_queue<pair<int, pair<int, int>>,
                    vector<pair<int, pair<int, int>>>,
                    cmp> pq;
    pq.push({0, {1, 1}});
    pair<int, pair<int, int>> x;
    int node, cost = 0;
    int T = N;
    while (T)
    {
        x = pq.top(), pq.pop();
        node = x.second.second;
        if (!father[node])
        {
            T--;
            cost += x.first;
            father[node] = x.second.first;
            for (i = 0; i < adjList[node].size(); i++)
            {
                if (!father[adjList[node][i].first])
                    pq.push({adjList[node][i].second, {node, adjList[node][i].first}});
            }
        }
    }

    ofstream g("apm.out");
    g << cost << '\n' << N - 1 << '\n';
    for (i = 1; i <= N; i++)
        if (father[i] != i)
            g << father[i] << ' ' << i << '\n';
    g.close();
    return 0;
}