#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define NMAX 200005
#define MMAX 400005

struct MUCHIE{
    int x, y, cost;
};

int n, m, h[NMAX], t[NMAX], costT, mT;
vector<MUCHIE>v, sol;

bool cmp(MUCHIE a, MUCHIE b){
    return (a.cost < b.cost);
}

int findSet(int a){
    while(a != t[a]){
        a = t[a];
    }
    return a;
}

void unite(int a, int b){
    if(h[a] == h[b]){
        t[b] = a;
        h[a]++;
    }else
    if(h[a] > h[b]){
        t[b] = a;
    }else{
        t[a] = b;
    }
}

int main(){

    int a, b, c, i, ta, tb;
    MUCHIE temp;
    FILE *fin, *fout;
    fin = fopen("apm.in", "r");
    fout = fopen("apm.out", "w");

    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d%d", &a, &b, &c);
        temp.x = a;
        temp.y = b;
        temp.cost = c;
        v.push_back(temp);
    }

    sort(v.begin(), v.end(), cmp);
    for(i=1; i<=n; i++){
        h[i] = 1;
        t[i] = i;
    }

    for(i=0; i<(int) v.size(); i++){
        a = v[i].x;
        b = v[i].y;
        c = v[i].cost;
        ta = findSet(a);
        tb = findSet(b);
        if(ta != tb){
            unite(ta, tb);
            sol.push_back(v[i]);
            costT += c;
        }
    }

    fprintf(fout, "%d\n%d\n", costT, (int)sol.size());
    for(i=0; i<(int) sol.size(); i++){
        fprintf(fout, "%d %d\n", sol[i].x, sol[i].y);
    }

    return 0;
}