#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200002
#define MAXE 400002
int n,m,cost,M[MAXN],F[MAXN];
struct muchie{
    int x,y,c;
}E[MAXE];
int comp(muchie a,muchie b){
    return a.c < b.c;
}
int find(int nod){
    int R=nod,aux;
    for(;F[R]!=0;R=F[R]);
    for(;nod!=R;aux=F[nod],F[nod]=R,nod=aux);
    return R;
}
bool APM(int X,int Y){
    int a=find(X),b=find(Y);
    if(a!=b)
        F[a]=b;
    return (a!=b);
}
void Kruskal(){
    int i;
    sort(E+1,E+m+1,comp);
    for(i=1;i<=m;i++){
        if(APM(E[i].x,E[i].y)){
            cost+=E[i].c;
            M[++M[0]]=i;
        }
    }
}
int main(){
    int i;
    freopen("apm.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d %d %d",&E[i].x,&E[i].y,&E[i].c);
    fclose(stdin);
    Kruskal();
    freopen("apm.out","w",stdout);
    printf("%d\n%d",cost,n-1);
    for(i=1;i<=M[0];++i)
        printf("\n%d %d",E[M[i]].x,E[M[i]].y);
    fclose(stdout);
    return 0;
}