#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream in ("apm.in");
ofstream out ("apm.out");

struct Muchie
{
    int x, y, cost;
};
struct Node
{
    int x, cost;
};

bool CompareMuchii(const Muchie& a, const Muchie& b)
{
    if (a.cost == b.cost)
    {
        if (a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    }
    return a.cost < b.cost;
}

vector<int> tata;
vector<int> level;

int Repr(int x)
{
    if (tata[x] == -1)
        return x;

    tata[x] = Repr(tata[x]);
    return tata[x];
}
void Reuniune(int x, int y)
{
    int repr_x = Repr(x);
    int repr_y = Repr(y);

    if (repr_x == repr_y)
        return;

    if (level[repr_x] <= level[repr_y])
    {
        tata[repr_x] = repr_y;
        if (level[repr_x] == level[repr_y])
            level[repr_y]++;
    }
    else
    {
        tata[repr_y] = repr_x;
        if (level[repr_x] == level[repr_y])
            level[repr_y]++;
    }
}

vector<Muchie> Kruskal(int n, vector<Muchie> &listaMuchii)
{
    tata.assign(n, -1);
    level.assign(n, 1);
    vector<Muchie> ans;

    sort(listaMuchii.begin(), listaMuchii.end(), CompareMuchii);
    int sel = 0;

    for (Muchie &m : listaMuchii)
    {
        cout << Repr(m.x) << Repr(m.y) << endl;
        if (Repr(m.x) == Repr(m.y)) continue;

        Reuniune(m.x, m.y);
        ans.push_back(m);
        sel++;

        if (sel == n - 1)
            break;
    }

    return ans;
}


int main()
{
    int n, m; in >> n >> m;
    vector<Muchie> listaMuchii(m);
    vector<vector<Node>> listaVecini(n);

    for (int i = 0; i < m; i++)
    {
        int x, y, cost; in >> x >> y >> cost;
        x--; y--;
        listaMuchii[i] = Muchie(x, y, cost);
        listaVecini[x].emplace_back(y, cost);
        listaVecini[y].emplace_back(x, cost);
    }

    vector<Muchie> apcm = Kruskal(n, listaMuchii);

    int totalCost = 0;
    for (Muchie &m : apcm)
        totalCost += m.cost;
    out << totalCost << "\n";
    out << apcm.size() << "\n";
    for (Muchie &m : apcm)
        out << m.x + 1 << " " << m.y + 1 << "\n";

    return 0;
}