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

using namespace std;

const int NMax = 2e5 + 5;
const int MMax = 4e5 + 5;

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

struct muchie
{
    int x, y, cost;
} v[MMax];

int tati[NMax];
vector< pair<int, int> > traseu;

bool sortare(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int N, M;

int Kruskal()
{
    int cost = 0;
    for (int i = 1; i <= N; i++)
        tati[i] = i;
    for (int i = 1; i <= M; i++)
    {
        int tx = tati[v[i].x];
        int ty = tati[v[i].y];
        if (tx != ty)
        {
            cost += v[i].cost;
            for (int j = 1; j <= N; j++)
                if (tati[j] == tx)
                    tati[j] = ty;
            traseu.push_back(make_pair(v[i].x, v[i].y));
        }
    }
    return cost;
}


int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        fin >> v[i].x >> v[i].y >> v[i].cost;
        //cout << v[i].x << " -> " << v[i].y << " - " << v[i].cost << endl;
    }
    sort(v + 1, v + M + 1, sortare);
    fout << Kruskal() << endl;
    fout << traseu.size() << endl;
    for (auto p : traseu)
    {
        fout << p.second << " " << p.first << endl;
    }
}