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

using namespace std;

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

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

vector <pair <int, int> > sol;

bool cmp(graf a, graf b)
{
    if(a.c > b.c)
        return 0;
    return 1;
}

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.push_back(make_pair(l[i].x, l[i].y));
        }
        if(nr >= n - 1) break;
    }
    fprintf(g,"%d\n%d\n",s,nr);
    for(int i = 0; i < nr; i++)
    {
        fprintf(g,"%d %d\n",sol[i].first, sol[i].second);
    }
    return 0;
}