#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

typedef struct
{
    int x,y,c;
} drum;

drum v[400000];
int n,m,i,x,y,a[200000],cost,poz;

bool ok(drum a, drum b)
{
    return a.c<b.c;
}

int find(int x)
{
    int t=x,p;
    while (t!=a[t]) t=a[t];
    while (x!=a[x]) p=a[x], a[x]=t, x=p;
    return x;
}

int main()
{
    f >> n >> m;
    for (i=0; i<m; i++) f >> v[i].x >> v[i].y >> v[i].c;
    sort(v,v+m,ok);
    for (i=1; i<=n; i++) a[i]=i;
    for (i=0; i<m; i++)
    {
        x=find(v[i].x);
        y=find(v[i].y);
        if (x!=y) a[x]=y, cost+=v[i].c, v[poz++]=v[i];
        if (poz==n-1) break;
    }
    g << cost << endl << poz << endl;
    for (i=0; i<poz; i++) g << v[i].x << ' ' << v[i].y << '\n';
}