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

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

const int N_max = 2e5 + 1;
const int M_max = 4e5 + 1;

int n, m, cost;

vector <int> tata(N_max, -1), dim(N_max, 1);

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

struct arbore
{
    int x, y;
} mst[N_max];

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

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

void union_sets(int nod1, int nod2) 
{
    nod1 = find_set(nod1);
    nod2 = find_set(nod2);
    if (nod1 == nod2)
        return;
    if (dim[nod1] < dim[nod2])
        swap(nod1, nod2);
    dim[nod1] += dim[nod2];
    tata[nod2] = nod1;
}

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

void kruskal()
{
    sort (a + 1, a + 1 + m, comp);

    int nr = 0;
    for (int i = 1; i <= m; ++i) 
    {
        if (find_set(a[i].x) != find_set(a[i].y)) 
        {
            union_sets(a[i].x, a[i].y);
            mst[++nr].x = a[i].x;
            mst[nr].y = a[i].y;
            cost += a[i].c;
        }
    }
}

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

int main()
{
    read();
    kruskal();
    print();

    fin.close();
    fout.close();
    return 0;
}