#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 verificare_tati(int ind, int from)
{
    if (tati[ind]==ind)
    {
        tati[ind]=from;
        return;
    }
    verificare_tati(tati[ind],from);
    tati[ind]=tati[tati[ind]];
}

void unire(int &from, int &to)
{
    verificare_tati(to,from);

   /* while (tati[from]!=from) {
        from = tati[from];
    }
    while (tati[to]!=to)
        to=tati[to];*/
}

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;
}