// #include <iostream>
// #include <vector>
// #include <algorithm>
// #include <fstream>

// using namespace std;

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

// struct Muchie
// {
//     int x, y, cost;
// };

// bool cmp(Muchie a, Muchie b)
// {
//     return a.cost < b.cost;
// }

// int n, m;
// vector<Muchie> muchii;
// int tata[200005];

// int gaseste(int x)
// {
//     if (tata[x] == x)
//         return x;
//     return tata[x] = gaseste(tata[x]);
// }

// int main()
// {
//     fin >> n >> m;

//     for (int i = 0; i < m; i++)
//     {
//         int u, v, c;
//         fin >> u >> v >> c;
//         muchii.push_back({u, v, c});
//     }

//     sort(muchii.begin(), muchii.end(), cmp);

//     for (int i = 1; i <= n; i++)
//     {
//         tata[i] = i;
//     }

//     int cost_total = 0;
//     vector<pair<int, int>> solutie;

//     for (int i = 0; i < m; i++)
//     {
//         int sef_x = gaseste(muchii[i].x);
//         int sef_y = gaseste(muchii[i].y);

//         if (sef_x != sef_y)
//         {
//             cost_total += muchii[i].cost;
//             solutie.push_back({muchii[i].x, muchii[i].y});

//             tata[sef_y] = sef_x;
//         }
//     }

//     fout << cost_total << "\n";
//     fout << n - 1 << "\n";
//     for (auto p : solutie)
//     {
//         fout << p.first << " " << p.second << "\n";
//     }

//     return 0;
// }

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

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

const long long INF = 1e18;
vector<pair<int, int>> adj[200005];
long long d[200005];
int tata[200005];
bool viz[200005];

int main()
{
    int n, m;

    fin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        adj[x].push_back({y, cost});
        adj[y].push_back({x, cost});
    }

    for (int i = 1; i <= n; i++)
        d[i] = INF;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<pair<int, int>> solutie;
    d[1] = 0;
    pq.push({0, 1});

    long long cost_total = 0;

    while (!pq.empty())
    {
        int u = pq.top().second;
        int cost_u = pq.top().first;
        pq.pop();

        if (viz[u])
            continue;
        if (tata[u] != 0)
        {
            solutie.push_back({u, tata[u]});
        }
        viz[u] = true;
        cost_total += cost_u;

        for (auto muchie : adj[u])
        {
            int v = muchie.first;
            int pondere = muchie.second;

            if (!viz[v] && pondere < d[v])
            {
                d[v] = pondere;
                tata[v] = u;
                pq.push({d[v], v});
            }
        }
    }
    fout << cost_total << endl;
    fout << n - 1 << endl;
    for (auto x : solutie)
    {
        fout << x.first << ' ' << x.second << endl;
    }
    return 0;
}