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

#define INF INT_MAX
using namespace std;


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

vector<int> p;
vector<vector<pair<int, int>>> adj;


int n, m, x, y, c, cTotal;

vector<int> keys;
vector<bool> marcat;

//struct cmp
//{
//    bool operator()(pair<int, int> a, pair<int, int> b)
//    {
//        return a.second < b.second;
//    }
//};


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()
{
    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] = INF;
    prim();

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