#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;


pair <int, int> aint[4 * NMAX];
int d[NMAX], tata[NMAX], n, m, a, b, c;
bool sel[NMAX];

pair <int, int> mymin(pair <int, int> a, pair <int, int> b)
{
    return (a.first < b.first ? a : b);
}

void update(int nod, int L, int R, int val, int poz)
{
    if(L == R){
        aint[nod] = {val, poz};
        return;
    }

    int mid = (L + R) >> 1;
    if(poz <= mid)
        update(2 * nod, L, mid, val, poz);
    else update(2 * nod + 1, mid + 1, R, val, poz);

    aint[nod] = mymin(aint[2 * nod], aint[2 * nod + 1]);
}

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 = 2; i <= n; i++)
        update(1, 1, n, INF, i), d[i] = INF;

    update(1, 1, n, 0, 1);
    d[1] = 0;

    for(int i = 1; i <= n; i++)
    {
        dmin = aint[1].first;
        poz = aint[1].second;
        update(1, 1, n, INF, poz);

        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;
                update(1, 1, n, it.cost, it.nod);
            }
        }
    }

    fout << sum << '\n' << n - 1 << '\n';
    for(int i = 1; i <= n; i ++)
        if(tata[i])
            fout << i << " " << tata[i] << '\n';

    return 0;
}