#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 200001;

struct muchie
{
    int x, y, cost;
};
muchie m[NMAX * 2];
int N, M, COST;
int ind[NMAX], GR[NMAX];

bool cmp(const muchie &m1, const muchie &m2)
{
    return m1.cost < m2.cost;
}
void citire()
{
    ifstream in ("apm.in");
    in >> N >> M;
    for (int i = 1; i <= M; i++)
        in >> m[i].x >> m[i].y >> m[i].cost;
    in.close();
}
int find(int i)
{
    if(GR[i] == i)
        return i;
    GR[i] = find(GR[i]);
    return GR[i];
}
void unite(int grn1, int grn2)
{
    GR[grn2] = grn1;
}
void kruskal(int n) //cu multimi disjuncte
{
    sort(m + 1, m + M + 1, cmp);
    for(int i = 1; i <= n; i++)
        GR[i] = i;
    COST = 0;
    for(int i = 1; n > 1; i++)
    {
        int grn1 = find(m[i].x), grn2 = find(m[i].y);
        if(grn1 != grn2)
        {
            ind[n] = i;
            COST += m[i].cost;
            unite(grn1, grn2);
            n--;
        }
    }
}
void afisare()
{
    ofstream out ("apm.out");
    out << COST << '\n' << N - 1 << '\n';
    for (int i = 2; i <= N; i++)
        out << m[ind[i]].x << ' ' << m[ind[i]].y << '\n';
    out.close();
}
int main()
{
    citire();
    kruskal(N);
    afisare();
    return 0;
}