#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

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

vector<vector<pair<int, int>>> lista;

void prim(int n)
{
    // {cost, {nod_curent, nod_parinte]}} => pair<int, pair<int, int>>
    // cost e primul pt că priority_queue sortează după prima valoare din pair
    // pq.top() returneaza elementul care este mai mic
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    vector<int> viz(n, 0);
    vector<pair<int, int>> apcm; // in total n - 1 muchii
    int costTotal = 0;
    int muchiiSelectate = 0;

    // incepem cu nodul 1, parinte -1, cost 0
    pq.push({0, {1, -1}});
    while(!pq.empty())
    {
        auto top = pq.top();
        pq.pop();

        int cost = top.first;
        int nod_curent = top.second.first;
        int nod_parinte = top.second.second;

        if(viz[nod_curent - 1] == 1)
            continue;
        viz[nod_curent - 1] = 1;

        if(nod_parinte != -1)
        {
            apcm.push_back({nod_curent, nod_parinte});
            costTotal += cost;
            muchiiSelectate++;
        }

        if(muchiiSelectate == n - 1)
            break;

        for(auto vecin : lista[nod_curent - 1])
        {
            // vector<pair<int, int>>
            int v = vecin.first;
            int c = vecin.second;
            if(viz[v - 1] == 0)
                pq.push({c, {v, nod_curent}});
        }
    }
    g << costTotal << "\n";
    g << apcm.size() << "\n";
    for(auto muchie : apcm)
        g << muchie.first << " " << muchie.second << "\n";
}

int main()
{
    int n, m, x, y, cost;
    f >> n >> m;
    lista.resize(n);
    for(int i = 0; i < m; i++)
    {
        f >> x >> y >> cost;
        lista[x - 1].push_back({y, cost});
        lista[y - 1].push_back({x, cost});
    }

    prim(n);
    return 0;
}