#include <bits/stdc++.h>
using namespace std;
using llx = long long;

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

vector<vector<pair<int, int>>> v;
vector<int> c_act, par;
vector<bool> viz;

int main()
{
    int n, m, i, x, y, z, j, rasp;

    fin >> n >> m;
    v.resize(n+1);
    c_act.assign(n+1, 1<<30), par.assign(n+1, -1), viz.assign(n+1, 0);
    for (i = 1; i<=m; i++)
    {
        fin >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }

    c_act[1] = 0;
    viz[1] = 1;
    for (const auto &it : v[1])
    {
        c_act[it.first] = it.second;
        par[it.first] = 1;
    }

    rasp = 0;
    for (i = 1; i<n; i++)
    {
        x = 0; // c_act[0] = 1<<30
        for (j = 1; j<=n; j++)
            if (viz[j] == 0 && c_act[j] < c_act[x])
                x = j;

        rasp += c_act[x];
        viz[x] = 1;

        for (const auto &it : v[x])
            if (viz[it.first] == 0 && c_act[it.first] > it.second)
            {
                c_act[it.first] = it.second;
                par[it.first] = x;
            }
    }

    fout << rasp << '\n' << n-1 << '\n';
    for (i = 2; i<=n; i++)
        fout << i << ' ' << par[i] << '\n';
    return 0;
}