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

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

vector< pair<int, int> > msp_edges; // minimum spanning tree's edges
vector< pair< pair<int, int>, int> > all_edges;
int v[nmax];
int n, m;

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

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

void merge_sets(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 sum= 0, x, y, w, number_of_msp_edges= 0;
    fin.sync_with_stdio(false);
    fin >> n >> m;
    for(int i=1; i<=n; i++) v[i]= -1;
    for(int i=1; i<=m; i++){
        fin >> x >> y >> w;
        all_edges.push_back(make_pair(make_pair(x, y), w));
    }
    sort(all_edges.begin(), all_edges.end(), cmp);
    int i= 0;
    while(number_of_msp_edges!= n-1){
        int node1= find_repr(all_edges[i].first.first);
        int node2= find_repr(all_edges[i].first.second);
        if(node1!= node2){
            sum+= all_edges[i].second;
            number_of_msp_edges++;
            merge_sets(node1, node2);
            msp_edges.push_back(make_pair(all_edges[i].first.first, all_edges[i].first.second));
        }
        i++;
    }
    fout << sum << "\n" << number_of_msp_edges << "\n";
    for(int i=0; i<msp_edges.size(); i++)   fout << msp_edges[i].first << " " << msp_edges[i].second << "\n";
    return 0;
}