#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 400001
struct muc{
    int x, y, c;
} v[MAX];
int tata[MAX], n, m, sol[MAX], grad[MAX], ns, sum;
bool cmp(muc a, muc b){return a.c<b.c;}
int uneste(int a, int b);
int findtata(int a);
int main()
{
    int i;
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
        scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].c);
    sort(v+1, v+m+1, cmp);
    for(i=1; i<=n; i++) tata[i] = i;
    for(i=1; i<=m; i++){
        int ok = uneste(v[i].x, v[i].y);
        if(ok) sol[++ns] = i, sum+=v[i].c;
    }
    printf("%d\n%d\n", sum, ns);
    for(i=1; i<=ns; i++) printf("%d %d\n", v[sol[i]].x, v[sol[i]].y);
    return 0;
}
int uneste(int a, int b){
    int ta, tb;
    ta = findtata(a);
    tb = findtata(b);
    if(ta!=tb){
        if(grad[ta]>grad[tb]) tata[tb] = ta, grad[ta]++;
        else tata[ta] = tb, grad[tb]++;
        return 1;
    }
    return 0;
}
int findtata(int a){
    if(a==tata[a])
        return a;
    else{
        int t = findtata(tata[a]);
        tata[a] = t;
        return t;
    }
}