#include<algorithm>
#include<cstdio>
using namespace std;

struct muchie
{
    int x, y, cost;
}v[400001], apm[200001];
int s, tata[200001], n, m, i, j;

bool comp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int radacina(int nod)
{
    if(!tata[nod])
        return nod;
    return radacina(tata[nod]);
}
int main(){
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","nod",stdout);
    scanf ("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf ("%d%d%d",&v[i].x,&v[i].y,&v[i].cost);
    sort(v+1,v+m+1,comp);
    j=1;
    for(i=1;i<=m &&j<n;i++)
        if (radacina(v[i].x)!=radacina(v[i].y)){
            tata[radacina(v[i].y)]=radacina(v[i].x);
            apm[j]=v[i];
            j++;
            s+=v[i].cost;
        }
    printf ("%d\n%d\n",s,n-1);
    for(i=1;i<n;i++)
        printf ("%d %d\n",apm[i].x,apm[i].y);
    return 0;
}