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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct drum{
    int from, to, cost;
}drumuri[400005];

bool cmp(drum a, drum b)
{
    return a.cost<b.cost;
}

vector<pair<int,int>>sol;
int n, m, tati[200005], suma;

void unire(int from, int to)
{
    while (tati[from]!=from)
        from=tati[from];
    while (tati[to]!=to)
        to=tati[to];
    tati[to]=from;
}

int baza(int ind)
{
    if(tati[ind]==ind)
    {
        return ind;
    }
    return baza(tati[ind]);
}

void verificare(int ind)
{
    if (baza(drumuri[ind].from)==baza(drumuri[ind].to))
    {
        return;
    }
    suma+=drumuri[ind].cost;
    sol.push_back({drumuri[ind].to,drumuri[ind].from});
    unire(drumuri[ind].from,drumuri[ind].to);
}

int main() {
    int from, to, cost;
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        tati[i]=i;
        f >> drumuri[i].from >> drumuri[i].to >>drumuri[i].cost;
    }
    sort(drumuri+1,drumuri+m+1, cmp);
    for (int i=1; i<=m; i++)
    {
        verificare(i);
    }
    g << suma << '\n';
    g << n-1 << '\n';
    for (auto &v:sol)
    {
        g << v.first <<' ' << v.second <<'\n';
    }
    return 0;
}