#include <bits/stdc++.h>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

const int MAXN=400010;
const int INF=2e9;

int n,m,parinte[MAXN],nrnod[MAXN],b[MAXN],c[MAXN];
vector <int> rez;

struct muchie{
    int x,y,cost,pos;
}a[MAXN];

bool comp1 (muchie x, muchie y){
    return x.cost<y.cost;
}
int radacina (int nod){
    if (parinte[nod]==nod)
        return nod;
    parinte[nod]=radacina (parinte[nod]);
    return parinte[nod];
}

void reuniune (int i, int j){
    if (nrnod[i]<nrnod[j])
        swap (i,j);
    parinte[j]=i;
    nrnod[i]+=nrnod[j];
}

int main()
{
    fin >>n>>m;
    for (int i=1;i<=m;++i){
        fin >>a[i].x>>a[i].y>>a[i].cost;
        a[i].pos=i;
        b[i]=a[i].x;
        c[i]=a[i].y;
    }

    sort (a+1,a+m+1,comp1);
    for (int i=1;i<=n;++i){
        parinte[i]=i;
        nrnod[i]=1;
    }

    int sum=0;

    for (int i=1;i<=m;++i){
        if (radacina (a[i].x)!=radacina (a[i].y)){

            sum+=a[i].cost;
            reuniune (radacina (a[i].x),radacina (a[i].y));
            rez.push_back (a[i].pos);

        }
        if (rez.size ()==n-1)
            break;

    }
    fout <<sum<<'\n'<<n-1<<'\n';
    for (int i=0;i<rez.size ();++i){
        fout <<b[rez[i]]<<' '<<c[rez[i]]<<'\n';
    }
    fin.close ();
    fout.close ();
    return 0;
}