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

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

vector <int> v;

int n, i, j, m, sum;

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

edge aux;
vector <edge> edges;

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

int find_root(int x){ // find the representative of each set
    if(v[x]<0)  return x;
    else{
        v[x] = find_root(v[x]);
        return (v[x]);
    }
}

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

int main(){
    fin >> n >> m;
    for(i=0; i<n; i++) v.push_back(-1);
    for(i=1; i<=m; i++){
        fin >> aux.x >> aux.y >> aux.weight;
        aux.x--;
        aux.y--;
        edges.push_back(aux);
    }

    sort(edges.begin(), edges.end(), cmp);

    for(i=0; i<m; i++){

        int a=find_root(edges[i].x);
        int b=find_root(edges[i].y);
        if(a!=b){
            quick_union(a, b);
            j++;
            sum+= edges[i].weight;
            }
        }
    cout << sum << "\n" << j << "\n";
    for(i=0; i<j; i++)  cout << edges[i].x+1 << " " << edges[i].y+1 << "\n";

    return 0;
}