#include <bits/stdc++.h>

using namespace std;

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

struct str
{
    int cost;
    int nod;
};

constexpr int NMAX = 2e5 + 3, INF = 1e9;

int d[NMAX], tata[NMAX], n, m, a, b, c;
bool sel[NMAX];

vector <str> G[NMAX];


int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        fin >> a >> b >> c;
        G[a].push_back({c, b});
        G[b].push_back({c, a});
    }

    int dmin, poz, sum = 0;

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

    for(int i = 1; i <= n; i++)
    {
        dmin = INF;
        for(int j = 1; j <= n; j++)
            if(d[j] < dmin && !sel[j])
                dmin = d[j], poz = j;

        sel[poz] = true;
        sum += dmin;

        for(auto it: G[poz]) {
            if(!sel[it.nod] && (it.cost < d[it.nod])) {
                d[it.nod] = it.cost;
                tata[it.nod] = poz;
            }
        }
    }
    sum = 0;
    for(int i = 2; i <= n; i++)
        sum += d[i];
    fout << sum << '\n' << n - 1 << '\n';
    for(int i = 1; i <= n; i ++)
        if(tata[i])
            fout << i << " " << tata[i] << '\n';

    return 0;
}