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

int v[nmax];
vector <pair<int, int> > final_edges;

struct edge{
    int x, y, value;
};

edge edges[nmax];

void get_data(int &n, int &m){
    ifstream fin("apm.in");
    fin >> n >> m;
    for(int i= 1; i<= m; i++)   fin >> edges[i].x >> edges[i].y >> edges[i].value;
}

bool cmp(edge x, edge y){
    return x.value< y.value;
}

void sort_data(int m){
    sort(edges+1, edges+m+1, cmp);
}

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

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

int put_things_together(int m, int n, int &nr){
    int apm_value= 0;
    nr= 0;
    sort_data(m);
    for(int i= 1; i<= n; i++)   v[i]= -1;
    for(int i= 1; i<= m; i++){
        int father_x= find_father(edges[i].x);
        int father_y= find_father(edges[i].y);
        if(father_x!= father_y){
            nr++;
            final_edges.push_back(make_pair(edges[i].x, edges[i].y));
            quick_union(father_x, father_y);
            apm_value+= edges[i].value;
            if(nr== n-1)    break;
        }
    }
    return apm_value;
}

void output_data(int n, int m){
    ofstream fout ("apm.out");
    int nr;
    fout << put_things_together(m, n, nr) << "\n";
    fout << nr << "\n";
    for(auto x: final_edges)    fout << x.first << " " << x.second << "\n";
}

int main(){
    int n, m, apm_value= 0;
    get_data(n, m);
    output_data(n, m);
    return 0;
}