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

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

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

struct edge2{
    int x, y;
};

int v[nmax];
edge edges[nmax];
int i, j, k, m , n, sum;
vector <edge2> subtree_edges;
edge2 aux;

bool cmp(edge a, edge b){
    return a.weight < b.weight;
}

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 find_representative(int x){
    if(v[x] < 0)    return x;
    else{
        v[x] = find_representative(v[x]);
        return (v[x]);
    }
}

int main(){
    fin >> n >> m;
    for(i=1; i<=n; i++) v[i]= -1;
    for(i=1; i<=m; i++){
        fin >> edges[i].x >> edges[i].y >> edges[i].weight;
    }
    sort(edges+1, edges+m+1, cmp);

    for(i=1; i<=m; i++){
        int a= find_representative(edges[i].x);
        int b= find_representative(edges[i].y);
        if(a != b){
            quick_union(a, b);
            j++;
            aux.x = edges[i].x;
            aux.y = edges[i].y;
            subtree_edges.push_back(aux);
            sum += edges[i].weight;
        }
    }
    fout << sum << "\n" << j << "\n";
    for(i=0; i<j; i++)  fout << subtree_edges[i].x << " " << subtree_edges[i].y << "\n";

    return 0;
}