#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>

#define NMax 200005
#define mod 1999999973
#define INF 0x3f3f3f3f
using namespace std;
struct muchie{
    int x,y,c;
}M[NMax];

int n,m,nr,vf1,vf2,ANS;
int sol[NMax],rang[NMax],rad[NMax];

int cmp(muchie x, muchie y){
    return (x.c < y.c);
}
int root(int k){
    while(rad[k] != k)
        k = rad[k];
    return k;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; ++i){
        scanf("%d%d%d",&M[i].x,&M[i].y,&M[i].c);
    }
    for(int i = 1; i <= n; ++i){
        rad[i] = i;
        rang[i] = 1;
    }
    sort(M + 1, M + 1 + m,cmp);
    for(int i = 1; i <= m && nr <= n - 1; ++i){
        vf1 = root(M[i].x);
        vf2 = root(M[i].y);

        if(vf1 != vf2){
            ANS += M[i].c;
            sol[++nr] = i;

            if(rang[vf1] > rang[vf2]){
                rang[vf1] += rang[vf2];
                rad[vf2] = rad[vf1];
            }else{
                rang[vf2] += rang[vf2];
                rad[vf1] = rad[vf2];
            }
        }
    }
    printf("%d\n",ANS);
    printf("%d\n",nr);
    for(int i = 1; i <= nr; ++i){
        printf("%d %d\n",M[sol[i]].x,M[sol[i]].y);
    }
    return 0;
}