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

using namespace std;

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

const int nmax = 200003;
int n, m;
int tata[nmax];
int rang[nmax];
vector <pair <int, int>> sol;
struct muchii{
    int x;
    int y;
    int cost;
    }edge[nmax];

void read(void);
void solve(void);
void unite(int x, int y);
int root(int x);
bool cmp(muchii a, muchii b){
    return a.cost < b.cost;
    }

int main(){
    int i;

    read();
    solve();
    }

void read(void){
    int a, x, y, i = 0, mcopie;
    
    fin>>n>>m;
    mcopie = m;

    while(mcopie--){
        fin>>x>>y>>a;
        edge[i].cost = a;
        edge[i].x = x;
        edge[i].y = y;
        i++;
        }

    sort(edge, edge + m, cmp);
    }

void unite(int x, int y){
    if(x != y){
        if(rang[x] == rang[y]){
            tata[x] = y;
            rang[x]++;
            }
        else if(rang[x] > rang[y])
            tata[x] = y;
        else tata[y] = x;
        }
    }

int root(int x){
    int radacina;

    if(!tata[x])
        return x;
    else{
        radacina = root(tata[x]);
        tata[x] = radacina;
        return radacina;
        }
    }   

void solve(void){
    int i, sum = 0, cnt = 0, rootx, rooty;

    for(i = 0; i < m; i++){
        rootx = root(edge[i].x);
        rooty = root(edge[i].y);
        if(rootx != rooty){
            sum += edge[i].cost;
            sol.push_back(make_pair(edge[i].x, edge[i].y));
            cnt++;
            unite(rootx, rooty);
            }
        }

    fout<<sum<<"\n"<<cnt<<"\n";
    for(i = 0; i < sol.size(); i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
    }