#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 200005
using namespace std;

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

vector< pair< pair<int, int>, int > > sorted;
int n, m;
int v[nmax];

bool cmp(pair< pair<int, int> , int > a, pair< pair<int, int> , int > b){
    return a.second < b.second;
}

int find_rep(int x){
    if(v[x]<0)  return x;
    else{
        v[x]= find_rep(v[x]);
        return v[x];
    }
}

void quick_union(int x, int y){
    if(v[x]>v[y]){
        v[y]+= v[x];
        v[x]= y;
    }
    else{
        v[x]+=v[y];
        v[y]= x;
    }
}

int main(){
    int x, y, w, sum=0, t=0;
    fin >> n >> m;
    for(int i=1; i<=n; i++) v[i]= -1;
    for(int i=1; i<=m; i++){
        fin >> x >> y >> w;
        sorted.push_back(make_pair(make_pair(x, y), w));
    }
    sort(sorted.begin(), sorted.end(), cmp);
    for(int i=0; i<=m; i++){
        int a= find_rep(sorted[i].first.first);
        int b= find_rep(sorted[i].first.second);
        if(a!=b){
            quick_union(a, b);
            sum+= sorted[i].second;
            t++;
        }
        if(t==n-1) break;
    }
    fout << sum << "\n" << t << "\n";
    for(int i=0; i<t; i++)  fout << sorted[i].first.second << " " << sorted[i].first.first << "\n";
    return 0;
}