#include <stdio.h>
#include <algorithm>
using namespace std;
int k,i,n,m;
int h[200005],t[200005];
struct cst{int x,y,c;} v[200005],sol[200005];
int cost,s;
int compare(cst a,cst b){return a.c<b.c;}
bool mch(int x,int y){
    int c,rx,ry;
    rx=x,ry=y;
    while(rx!=t[rx]) rx=t[rx];
    while(ry!=t[ry]) ry=t[ry];
    int aux,tx=x,ty=y;
    while(tx!=rx){aux=tx;tx=t[aux];t[aux]=rx;}
    while(tx!=rx){aux=ty;ty=t[aux];t[aux]=ry;}
    if(rx==ry) return 0;
    if(h[rx]<h[ry]){t[rx]=ry; c=ry; }
    else {t[ry]=rx;c=rx;}
    if(h[rx]==h[ry]) h[c]++;
}
int main()
{
   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,compare);
    for(i=1;i<=n;i++) h[i]=1,t[i]=i;
    i=0;
    k=1;
    while(k<=n-1){
       if(mch(v[i].x,v[i].y)){
            cost+=v[i].c;
        sol[++s]=v[i];
        k++;
       }
        i++;
    }
    printf("%d\n%d\n",cost,k-1);
    for(i=1;i<=k-1;i++) printf("%d %d\n",sol[i].x,sol[i].y);
    return 0;
}