#include <stdio.h>
#include <algorithm>
#define MAX 200002
using namespace std;
struct muchie{ int x,y,c; }u[2*MAX];
int rad[MAX],n,m,sol=0;
bool ok[MAX];

bool cmp(muchie a,muchie b){ return a.c<b.c; }

int tata(int x){
    while(x!=rad[x])x=rad[x];
    return x; }

void APM(){
    int i=1;
    for(int k=1;k<n;k++){
        while(tata(u[i].x)==tata(u[i].y))i++;
        ok[i]=1;
        sol+=u[i].c;
        rad[tata(u[i].x)]=tata(u[i].y); }
}

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",&u[i].x,&u[i].y,&u[i].c);

        sort(u+1,u+m+1,cmp);
        for(int i=1;i<=n;i++)rad[i]=i;
        APM();
        printf("%d\n",sol);
        printf("%d\n",n-1);
        for(int i=1;i<=m;i++)
        if(ok[i])printf("%d %d\n",u[i].x,u[i].y);
}