#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
void unire(int x, int y);
int sef(int x);




struct ura
{
    int x, y, c;
}v[400001];
int tata[200001];

struct ura2
{
    int x, y;
}sol[400001];

bool cmp(ura a, ura b)
{
    if(a.c <= b.c)
    {
        return true;
    }
    return false;
}



int main()
{
    int n, m, i, luate = 0, cost = 0, cnt = 0;
    in >> n >> m;
    for(i = 1; i <= m; i++)
    {
        in >> v[i].x >> v[i].y >> v[i].c;
    }
    for(i = 1; i <= n; i++)
    {
        tata[i] = i;
    }
    sort(v + 1, v + m + 1, cmp);
    i = 1;
    while(luate < n - 1)
    {
        if(sef(v[i].x) != sef(v[i].y))
        {
            unire(v[i].x, v[i].y);
            cost += v[i].c;
            luate++;
            sol[++cnt].x = v[i].x;
            sol[cnt].y = v[i].y;
        }
        i++;
    }
    out << cost << '\n';
    out << cnt << '\n';
    for(i = 1; i <= cnt; i++)
    {
        out << sol[i].x << " " << sol[i].y << '\n';
    }
    return 0;
}

void unire(int x, int y)
{
    int sefx = sef(x);
    int sefy = sef(y);
    tata[sefx] = sefy;
}

int sef(int x)
{
    if(tata[x] == x)
    {
        return x;
    }
    else
    {
        return tata[x] = sef(tata[x]);
    }
}