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

struct muchii{
    int a, b, cost;
}aux;

int n, m, padre[nmax], depth[nmax], sum = 0, branches = 0;
vector <muchii> G;
muchii tree[mmax];

void initialise(){
    for(int i=1; i<=n; i++){
        padre[i] = i;
        depth[i] = 1;
    }
}

bool cmp(muchii m1, muchii m2){
    return (m1.cost < m2.cost);
}

int find_parent(int x){
    while(x != padre[x])
        x = padre[x];
    return x;
}

void unite(int x, int y){
    x = find_parent(x);
    y = find_parent(y);
    if(depth[x] > depth[y])
        padre[y] = x;
    else
        if(depth[x] < depth[y])
            padre[x] = y;
        else{
            padre[y] = x;
            depth[x]++;
        }
}

void solve(){
    ifstream f("apm.in");
    f >> n >> m;
    initialise();
    for(int i=1; i<=m; i++){
        f >> aux.a >> aux.b >> aux.cost;
        G.push_back(aux);
    }
    sort(G.begin(), G.end(), cmp);
    for(int i=0; i<m; i++){
        if(find_parent(G[i].a) != find_parent(G[i].b)){
            sum += G[i].cost;
            unite(G[i].a, G[i].b);
            branches++;
            tree[branches].a = G[i].a;
            tree[branches].b = G[i].b;
        }
    }
}

void display(){
    ofstream g("apm.out");
    g << sum << "\n" << branches << "\n";
    for(int i=1; i<=branches; i++)
        g << tree[i].a << " " << tree[i].b << "\n";
}

int main()
{
    solve();
    display();
    return 0;
}