#include <stdio.h>
#include <vector>
#include <algorithm>
#define MAx 400100

using namespace std;

int n, m, t[MAx];
FILE*f=fopen("apm.in","r"),*g=fopen("apm.out","w");

struct graf
{
    int x, y,c;
}l[MAx],sol[MAx];


bool cmp(graf a, graf b)
{
        return a.c < b.c;
}

int tata(int k)
{
    if(t[k] == k)
        return k;
    int h = tata(t[k]);
    t[k] = h;
    return h;
}

int main()
{
    int x, y, c;
    fscanf(f,"%d %d",&n,&m);
    for(int i = 1; i <= m; i++)
    {
        fscanf(f,"%d %d %d",&l[i].x,&l[i].y,&l[i].c);
        if(i <= n)
            t[i] = i;
    }
    t[n] = n;
    sort(l + 1, l + m + 1, cmp);
    int s = 0, tx, ty, nr = 0;
    for(int i = 1; i <= m; i++)
    {
        tx = tata(l[i].x);
        ty = tata(l[i].y);
        if(tx != ty)
        {
            t[tx] = ty;
            s += l[i].c;
            nr++;
            sol[nr].x = l[i].x;
            sol[nr].y = l[i].y;
         }
        if(nr == n - 1) break;
    }
    fprintf(g,"%d\n%d\n",s,nr);
    for(int i = 1; i <= nr; i++)
    {
        fprintf(g,"%d %d\n",sol[i].x, sol[i].y);
    }
    return 0;
}