#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int NMAX = 200000;

vector<pair<int, int>> graf[1 + NMAX];

bool vizitat[1 + NMAX];

priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;

vector<pair<int, int>> muchiiLuate;

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");

    int n, m;

    in >> n >> m;

    for (int j = 1; j <= m; j++)
    {
        int x, y, c;

        in >> x >> y >> c;

        graf[x].emplace_back(make_pair(y, c));
        graf[y].emplace_back(make_pair(x, c));
    }

    int solCost = 0;

    pq.emplace(make_pair(0, make_pair(0, 1)));

    while (!pq.empty())
    {
        int cost = pq.top().first;
        int anterior = pq.top().second.first;
        int nod = pq.top().second.second;

        pq.pop();

        if (vizitat[nod])
        {
            continue;
        }

        vizitat[nod] = true;

        solCost += cost;

        muchiiLuate.emplace_back(make_pair(anterior, nod));

        for (int i = 0; i < graf[nod].size(); i++)
        {
            if (!vizitat[graf[nod][i].first])
            {
                pq.emplace(make_pair(graf[nod][i].second, make_pair(nod, graf[nod][i].first)));
            }
        }
    }

    out << solCost << '\n' << muchiiLuate.size() - 1 << '\n';

    for (int i = 1; i < muchiiLuate.size(); i++)
    {
        out << muchiiLuate[i].first << ' ' << muchiiLuate[i].second << '\n';
    }

    return 0;
}