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

ifstream f ("apm.in");
ofstream g ("apm.out");
const int MMax = 400005;
pair <int, int> P[MMax];
int k;
int n, m, total;
//int tt[MMax], rg[MMax];
struct muchie{
    int x, y, cost;
};
vector<int> tt;
vector<int> rg;
vector<muchie> v;
bool compare(muchie a, muchie b){
    return a.cost < b.cost;
};
void read(){
    f >> n >> m;
    int i;
    muchie temp;
    for (i=1; i<=m; i++){
        f >> temp.x >> temp.y >> temp.cost;
        v.push_back(temp);
    }
    // sortare dupa cost
    sort (v.begin(), v.end(), compare);
    // init vector de tata si rang
    // pentru pozitia 0
    rg.push_back(0);
    tt.push_back(0);
    for (i=1; i<=n; i++ ){
        rg.push_back(1);
        tt.push_back(i);
    }
//    for (auto x: v){
//        cout << x.x << " " << x.y << " " << x.cost << endl;
//    }

}
// verificare de tata
// cautarea se incheie in momentul in care
// tatal nodului curent este nodul curent

int find (int nod){
    while (tt[nod] != nod) {
        //urc pe vector
        nod = tt[nod];
    }
    return nod;
}
// legam arborele mai micut de arborele mai mare
void unire (int x, int y){
    if (rg[x] < rg[y])
        tt[x] = y;
    if (rg[x] > rg[y])
        tt[y] = x;
    if (rg[x] == rg[y]){
        tt[x] = y;
        //crestem rangul arborelui
        rg[y] ++;
    }
}
void rezolvare (){
    int i;
    int tataX, tataY;
    for (i=0; i<m; i++){
        tataX = find(v[i].x);
        tataY = find(v[i].y);
        if ( tataX != tataY ){
            // cazul cand au tati diferiti
            unire(tataX, tataY);
            P[++k].first = v[i].x;
            P[k].second = v[i].y;
            total += v[i].cost;
        }
    }
}
void afisare (){
    g << total << endl << n-1 << endl;
    int i;
    for (i=1; i<=k ;i++)
        g << P[i]. first << " " << P[i].second << endl;
}
int main (){
    read();
    rezolvare();
    afisare();
    return 0;
}