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

using namespace std;

#define INT_MAX 0x7fffffff

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

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 min = INT_MAX, pozMin = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (keys[i] < min && !marcat[i])
            min = keys[i], pozMin = i;
    }
    cTotal += min;
    return pozMin;
}


void prim()
{
    for (int i = 1; i <= n; ++i)
    {
        int vf = extract_min();
        marcat[vf] = true;
        for (const auto& vec : adj[vf])
        {
            if (keys[vec.first] > vec.second && !marcat[vec.first])
            {
                keys[vec.first] = vec.second;
                p[vec.first] = 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;
}