#include<algorithm>
#include<cstdio>
using namespace std;
struct mazi{int c,x,y;};
mazi v[400001];
mazi k[200001];
int t[200001];
int s;
bool meow(mazi a,mazi b){
    if (a.c<b.c) return true;
    return false;
}
int rad(int w){
    if (t[w]==0) return w;
    t[w]=rad(t[w]);
    return t[w];
}
int main(){
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    int n,m,i,j;
    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,meow);
    j=1;
    for(i=1;i<=m &&j<n;i++)
        if (rad(v[i].x)!=rad(v[i].y)){
            t[rad(v[i].y)]=rad(v[i].x);
            k[j]=v[i];
            j++;
            s+=v[i].c;
        }
    printf ("%d\n%d\n",s,n-1);
    for(i=1;i<n;i++)
        printf ("%d %d\n",k[i].x,k[i].y);
    return 0;
}