#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define dim 200001

using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

struct filip
{
    int x,y,c;
}v[400001];

int n,m,i,poz[dim],k,ix,iy,cost,j;
vector < pair < int,int > > vec;

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

int main()
{
    f >> n >> m;
    for(i = 1;i <= m;i++)
        f >> v[i].x >> v[i].y >> v[i].c,poz[i] = i;
    sort(v + 1,v + m + 1,cmp);
    for(i = 1;k < n - 1;i++)
    {
        ix = poz[v[i].x];
        iy = poz[v[i].y];
        if(ix != iy)
        {
            k++;
            cost += v[i].c;
            vec.push_back(make_pair(v[i].x,v[i].y));
        }
        for(j = 1;j <= n;j++)
            if(poz[j] == iy)
            poz[j] = ix;
    }
    g << cost << '\n' << k << '\n';
    for(i = 0;i < k;i++)
        g << vec[i].first << " " << vec[i].second << '\n';
    return 0;
}