#include <algorithm>
#include <fstream>

using namespace std;

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


struct muchie
{
    int x, y, c;
};


const int N = 200001;
const int M = 400001;

int n, m;
int T[N], rang[N];
muchie muchii[M];
bool ok[N];
int rez;
int sol[M];
int q;

inline bool cmp(muchie m1, muchie m2)
{
    return m1.c < m2.c;
}

inline int multime(int nod)
{
    if(T[nod] != nod)
        T[nod] = multime(T[nod]);
    return T[nod];
}

void reuneste(int i, int j)
{
    i = multime(i);
    j = multime(j);

    if(i == j)
        return;

    if(rang[i] < rang[j])
        T[i] = j;
    else
        T[j] = i;

    if(rang[i] == rang[j])
        rang[i]++;
}

void citire()
{
    q = 0;
    rez = 0;

    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        muchii[i] = (muchie){x, y, c};
    }

    sort(muchii + 1, muchii + m + 1, cmp);

    for(int i = 1; i <= n; i++)
    {
        T[i] = i;
        rang[i] = 0;
    }
}

void kruskal()
{
    for(int k = 1; k <= m; k++)
    {
        int i = muchii[k].x;
        int j = muchii[k].y;
        int cost = muchii[k].c;

        if(multime(i) != multime(j))
        {
            reuneste(i, j);
            rez += cost;

            sol[++q] = k;
        }
    }
}

void afisare()
{
    out << rez << '\n' << n - 1 << '\n';

    for(int i = 1; i <= q; i++)
        out << muchii[sol[i]].x << ' ' << muchii[sol[i]].y << '\n';
}

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}