#include <iostream>
#include <vector>
#include <utility>
#include <fstream>
#include <limits.h>

using namespace std;

int *sp;
pair<int,pair<int,int> > *p;
pair<int,int> *r;

int findsp(int x) {
    if (sp[x] == x) return x;
    else return sp[x] = findsp(sp[x]);
}

void unite(int x, int y) {
    int tx,ty;
    tx = findsp(x);
    ty = findsp(y);
    sp[tx] = ty;
}

int main()
{
    ifstream f("apm.in");
    int n,m,x,y,c,i,cost,j,h;
    cost = 0;
    f>>n>>m;
    r = new pair<int,int>[n-1];
    sp = new int[n+1];
    for (i=1;i<=n;i++) sp[i] = i;
    p = new pair<int,pair<int,int> >[m];
    f>>x>>y>>c;
    p[0] = make_pair(x,make_pair(y,c));
    for (i=1;i<m;i++) {
        f>>x>>y>>c;
        j = 0;
        while (p[j].second.second < c && p[j].first != 0) j++;
        for (h=m-1;h>=j;h--) p[h] = p[h-1];
        p[j] = make_pair(x,make_pair(y,c));
    }
    f.close();
    c = 0;
    j = 0;
    while (c < n-1) {
        x = findsp(p[j].first);
        y = findsp(p[j].second.first);
        if (x == y) {
            j++;
            continue;
        }
        unite(p[j].first,p[j].second.first);
        cost += p[j].second.second;
        r[c] = make_pair(p[j].first,p[j].second.first);
        c++;
        j++;
    }
    ofstream g("apm.out");
    g<<cost<<endl;
    g<<c<<endl;
    for (i=0;i<c;i++) g<<r[i].first<<" "<<r[i].second<<endl;
    return 0;
}