#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int const nmax=200000;
int const mmax=400000;

struct muchie{
    int n1, n2, c;
};

int tati[nmax+1];
muchie edge[mmax+1];
vector<muchie> rasp;

int root(int nod){
    if (tati[nod]==nod)
       return nod;
    return tati[nod]=root(tati[nod]);
}
void join(int n1, int n2){
    int r1=root(n1), r2=root(n2);
    tati[r2]=r1;
}
bool cmp(muchie a, muchie b){
    return a.c<b.c;
}
void afisedge(int m){
    for (int i=1; i<=m; i++)
        cout << edge[i].n1 << ' ' << edge[i].n2 << ' ' << edge[i].c << '\n';
}
void afistati(int n){
    for (int i=1; i<=n; i++)
        cout << tati[i] << ' ';
    cout << endl;
}

int main(){
    int n, m, cost=0, n1, n2, c;
    in >> n >> m;
    for (int i=1; i<=n; i++)
        tati[i]=i;
    for (int i=1; i<=m; i++){
        in >> n1 >> n2 >> c;
        edge[i]={n1, n2, c};
    }
    sort(edge+1, edge+m+1, cmp);
//    afistati(n);
//    afisedge(m);
    for (int i=1; i<=m && rasp.size()!=n-1; i++){
        if (root(edge[i].n1)!=root(edge[i].n2)){
            join(edge[i].n1, edge[i].n2);
//            afistati(n);
            rasp.push_back(edge[i]);
            cost+=edge[i].c;
        }
    }
    out << cost << '\n' << n-1 << '\n';
    for (int i=0; i<rasp.size(); i++)
        out << rasp[i].n1 << ' ' << rasp[i].n2 << '\n';
}