#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

#define INT_MAX 0xffffffff

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

vector<int> p;
vector<vector<pair<int, int>>> adj;
vector<int> keys;
vector<bool> marcat;
int n, m, x, y, c, cTotal;


int extract_min()
{
    int minn = INT_MAX, pozMin = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (keys[i] < minn && !marcat[i])
            minn = keys[i], pozMin = i;
    }
    cTotal += minn;
    return pozMin;
}


void prim()
{
    int ant = 0;
    for (int i = 1; i <= n; ++i)
    {
        int vf = extract_min();
        marcat[vf] = true;
        p[vf] = ant;
        for (const auto& vec : adj[vf])
        {
            if (keys[vec.first] > vec.second)
                keys[vec.first] = vec.second;
        }
        ant = vf;
    }
}


int main(int argc, char* argv[])
{
    fin >> n >> m;
    adj.resize(n + 1);
    p.resize(n + 1);
    keys.resize(n + 1);
    marcat.resize(n + 1);
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> c;
        adj[x].push_back(make_pair(y, c));
        adj[y].push_back(make_pair(x, c));
    }
    keys[1] = 0;
    for (int i = 2; i <= n; ++i)
        keys[i] = INT_MAX;
    prim();

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