#include <cstdio>
#include <algorithm>
using namespace std;
#define Max 200001

struct edge{ int x,y,c; } u[2*Max];
int rad[Max],n,m;
bool was[2*Max];

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

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

void apm(){
    for(int i=1;i<=n;i++) rad[i] = i;

    int i = 1, cst = 0;
    for(int k=1;k<n;k++)
    {
        while(tata(u[i].x)==tata(u[i].y))i++;
        cst += u[i].c;
        was[i] = 1;
        rad[tata(u[i].x)] = tata(u[i].y);
        i++;
    }
    printf("%d\n",cst);
    printf("%d\n",n-1);
    for(int i=1;i<=m;i++)
    if( was[i] )printf("%d %d\n",u[i].x, u[i].y);
}

int main(){
    int x,y;

    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,sort_type);

    apm();

    return 0;
}