#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

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) { ///returneaza rad subarborelui in care se afla nodul x
    int r=x,j;
    while(t[r]!=r) r=t[r]; ///radacina subarborelui lui x
    t[x]=r;
    return r;
}

void unif(int x,int y) { ///unif subarborilor de rad x cu subarbore de rad 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;
    g<<ct<<'\n'<<k<<'\n';
    for (i=1;i<=k;i++)
        g<<u[sol[i]].x<<' '<<u[sol[i]].y<<'\n';
}

int muchie(int x,int y) {
    int r1,r2,x1,x2,c;
    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,j,x,y,z;
    f>>n>>m;
    for (i=1;i<=m;i++) {
        f>>x>>y>>z;
        u[i].x=x;
        u[i].y=y;
        u[i].c=z;
    }
    init();
    sort(u+1,u+m+1,comp);
    kruskal();
    afis();
    return 0;
}