#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

vector<pair<int, int>> G[105];

priority_queue<pair<int, pair<int, int>>> PQ;
vector<pair<int, int>> muchii;
int tata[105];
bool viz[105];
int cost;

void prim(int n) {
    for(auto it : G[1]) {
        PQ.push({-it.second, {it.first, 1}});
    }

    viz[1] = 1;
    tata[1] = 0; // Radacina (data de problema)

    int nr = 0;
    while(nr < n-1) {
        int nod = PQ.top().second.first;
        int prev = PQ.top().second.second;
        int c = -PQ.top().first;
        PQ.pop();

        if(!viz[nod]) {
            viz[nod] = 1;
            nr++;
            cost += c;
            muchii.push_back({nod, prev});
            tata[nod] = prev;

            for(auto it : G[nod]) {
                if(!viz[it.first]) {
                    PQ.push({-it.second, {it.first, nod}});
                }
            }
        }
    }
}

int main()
{
    int n, m, x, y, c;
    fin>>n>>m;

    for(int i = 1; i<=m; i++) {
        fin>>x>>y>>c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }

    prim(n);

    fout << cost << '\n';
    fout << n - 1 << '\n';
    for (auto it : muchii) {
        fout << it.first << ' ' << it.second << '\n';
    }

    return 0;
}