#include <fstream>
#include <algorithm>

using namespace std;

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

const int M = 400005;
const int N = 200005;

struct muchie
{
    int x, y, cost;
};
muchie m[M];

bool cmp(muchie a, muchie b)
{
    return (a.cost < b.cost);
}
int tata[N], niv[N];

void Union(int r1, int r2)
{
    if(niv[r1] < niv[r2])
        tata[r1] = r2;
    else if(niv[r2] < niv[r1])
        tata[r2] = r1;
    else
    {
        tata[r1] = r2;
        niv[r2] ++;
    }
}

int Find(int x)
{
    int rad = x, y;
    while(tata[rad] != rad)
        rad = tata[rad];
    while(tata[x] != x)
    {
        y = tata[x];
        tata[x] = rad;
        x = y;
    }
    return rad;
}

int solx[N], soly[N];

int main()
{
    int n, edg;
    in >> n >> edg;
    int i;
    for(i = 1; i <= edg; i++)
        in >> m[i].x >> m[i].y >> m[i].cost;
    sort(&m[1], &m[edg+1], cmp);
    for(i = 1; i <= n; i++)
        tata[i] = i;
    int rad1, rad2;
    int costmin = 0, cnt = 0;
    for(i = 1; i <= edg; i++)
    {
        rad1 = Find(m[i].x);
        rad2 = Find(m[i].y);
        if(rad1 != rad2)
        {
            Union(rad1, rad2);
            costmin += m[i].cost;
            cnt ++;
            solx[cnt] = m[i].x;
            soly[cnt] = m[i].y;
        }
    }
    out << costmin << "\n" << n-1 <<"\n";
    for(i = 1; i <= n-1; i++)
        out << solx[i] << " " << soly[i] <<"\n";
    return 0;
}