#include <fstream>
#include <algorithm>
using namespace std;

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

const int n_Max = 200001;
const int m_Max = 400001;

int n, m, cost;

struct muchii
{
    int x, y, c;
} a[m_Max];

struct arbore
{
    int x, y;
} b[n_Max];

int tata[n_Max], dim[n_Max];

void initializare()
{
    for (int i = 1; i <= n; ++i)
    {
        tata[i] = -1;
        dim[i] = 1;
    }
}

void citire()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
        fin >> a[i].x >> a[i].y >> a[i].c;
}

int find_set(int x)
{
    if (tata[x] == -1)
        return x;
    return tata[x] = find_set(tata[x]);
}

void sets_union(int x, int y)
{
    if (dim[x] < dim[y])
        swap(x, y);
    dim[x] += dim[y];
    tata[y] = x; 
}

bool comp(muchii a, muchii b)
{
    return a.c < b.c;
}

void kruskal()
{
    initializare();
    sort(a + 1, a + 1 + m, comp);
    int nr = 0;
    for (int i = 1; i <= m; ++i)
    {
        int x = find_set(a[i].x);
        int y = find_set(a[i].y);
        if (x != y)
        {
            sets_union(x, y);
            cost += a[i].c;
            b[++nr].x = a[i].x;
            b[nr].y = a[i].y;
        }
    }
}

void afisare()
{
    fout << cost << "\n" << n - 1 << "\n";
    for (int i = 1; i < n; ++i)
        fout << b[i].x << " " << b[i].y << "\n";
}

int main()
{
    citire();
    kruskal();
    afisare();
    fin.close();
    fout.close();
    return 0;
}