#include<bits/stdc++.h>
using namespace std;

FILE*f=fopen("apm.in","r");
FILE*g=fopen("apm.out","w");

int n,l[200005],t[200005],m,h[200005],ct,sol[200005],k;
struct mch{
    int x,y,c;
} u[400005];

int findd(int x) {
    int r=x;
    while(t[r]!=r) r=t[r];
    t[x]=r;
    return r;
}

void unif(int x,int y) {
    int c;
    if (h[x]<h[y]) {
        t[x]=y;
        c=y;
    }
    else {
        t[y]=x;
        c=x;
    }
    if (h[x]==h[y]) h[c]++;
}

void init() {
    int i;
    for (i=1;i<=n;i++)
        h[i]=1;
    for (i=1;i<=n;i++)
        t[i]=i;
}

void afis() {
    int i;
    fprintf(g,"%d\n%d\n",ct,k);
    for (i=1;i<=k;i++)
        fprintf(g,"%d %d\n",u[sol[i]].x,u[sol[i]].y);
}

int muchie(int x,int y) {
    int r1,r2;
    r1=findd(x);
    r2=findd(y);
    if (r1==r2) return 0;
    unif(r1,r2);
    return 1;
}

void kruskal() {
    int i=1;
    while (k<n-1) {
        if (muchie(u[i].x,u[i].y)) {
            ct+=u[i].c;
            sol[++k]=i;
        }
        i++;
    }
}

int comp(mch x,mch y) {
    return x.c<y.c;
}

int main() {
    int i;
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++) fscanf(f,"%d%d%d",&u[i].x,&u[i].y,&u[i].c);
    init();
    sort(u+1,u+m+1,comp);
    kruskal();
    afis();

    fclose(f); fclose(g);

    return 0;
}