#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 200002

int rad[MAX],n,m,cost=0;
struct edge{ int x,y,c; }g[2*MAX];
bool viz[2*MAX];

bool comp(edge a,edge b){ return a.c<b.c; }

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

void apm(){
    int i;
    sort(g,g+m,comp);
    for(int i=1;i<=n;i++)rad[i]=i;
    i=0;
    for(int k=1;k<n;k++)
    {
        while(tata(g[i].x)==tata(g[i].y))i++;
        cost+=g[i].c;
        viz[i]=1;
        rad[tata(g[i].x)]=tata(g[i].y);
        i++;
    }
}

int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=0;i<m;i++)scanf("%d %d %d",&g[i].x,&g[i].y,&g[i].c);
    apm();
    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(int i=0;i<m;i++)
    if(viz[i])printf("%d %d\n",g[i].x,g[i].y);

    return 0;
}