#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

int tata[100001], niv[1000001];
struct muchie{
    int x, y, cost;
}v[400001];

vector <muchie> arb;

int cmp(muchie m1, muchie m2){
    return m1.cost < m2.cost;
}
int cautare(int nod){
    int cpnod = nod, rad = nod;
    while(tata[rad] != 0){
        rad = tata[rad];
    }
    while(tata[cpnod] != 0){
        int aux = tata[cpnod];
        tata[cpnod] = rad;
        cpnod = aux;
    }
    return rad;
}

void reuniune(int x, int y){
    int t1 = cautare(x);
    int t2 = cautare(y);
    if(niv[t1] < niv[t2]){
        tata[t1] = t2;
    }
    else if(niv[t2] < niv[t1]){
        tata[t2] = t1;
    }
    else{
        tata[t1] = t2;
        niv[t2]++;
    }
}

int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= m; i++){
        in >> v[i].x >> v[i].y >> v[i].cost;
    }
    sort(v + 1, v + m + 1, cmp);
    int nr = 0; //cate muchii am pus
    int cost = 0;
    for(int i = 1; i <= m && nr < n - 1; i++){
        int t1 = cautare(v[i].x);
        int t2 = cautare(v[i].y);
        if(t1 != t2){
            nr++;
            arb.push_back(v[i]);
            reuniune(t1, t2);
            cost += v[i].cost;
        }
    }
    out << cost <<'\n' << nr << '\n';
    for(int i = 0; i < arb.size(); i++){
        out << arb[i].x<<' '<<arb[i].y<<'\n';
    }

    return 0;
}