#include<cstdio>
#include<algorithm>
using namespace std;
pair<int,int> cost[200001], a[200001], sol[200001];
int i, n, m, nr, tt[200001], grad[200001], costf;
int find(int x){
    int i=x, y;
    while (tt[i]!=i) i=tt[i];
    while (tt[x]!=x) {y=tt[x]; tt[x]=i; x=y;}
    return i;
}
void unite(int x, int y){
    if (grad[x]>grad[y]) tt[x]=y; else tt[y]=x;
    if (grad[x]==grad[y]) grad[x]++;
}
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (i=1;i<=n;i++) {tt[i]=i; grad[i]=1;}
    for (i=1;i<=m;i++) {
        scanf("%d%d%d", &a[i].first, &a[i].second, &cost[i].first); cost[i].second=i;
    }
    sort(cost+1, cost+m+1); nr=0; costf=0;
    for (i=1;nr!=n-1;i++) {
        if (find(a[cost[i].second].first)!=find(a[cost[i].second].second)) {
            unite(find(a[cost[i].second].first), find(a[cost[i].second].second));
            costf+=cost[i].first; nr++; sol[nr]=a[cost[i].second];
        }
    }
    printf("%d\n%d\n", costf, nr);
    for (i=1;i<n;i++) printf("%d %d\n", sol[i].first, sol[i].second);
    return 0;
}