//kruskal
#include<cstdio>
#include<algorithm>
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","w",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);
    for(i=1, j=1; i<=m && j<n; i++)
        if(radacina(v[i].x) != radacina(v[i].y))
            {
                tata[radacina(v[i].x)]=radacina(v[i].y);
                apm[j++]=v[i];
                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;
}