#include <bits/stdc++.h>
#define NMAX 200005

using namespace std;

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

struct A
{
    int x, y, cost;
};

struct B
{
    int x, y;
};

struct crt
{
    bool operator()(A a, A b)
    {
        if(a.cost < b.cost) return 1;
        else return 0;
    }
};

multiset < A, crt > a;
vector < B > r;
int t[NMAX], lg[NMAX];

void uneste(int x, int y);
int radacina(int x);

int main()
{
    multiset < A, crt > :: iterator it;
    vector < B > ::iterator itt;
    A el;
    int n, m, x, y, z, i, s = 0;

    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y >> z;
        a.insert({x, y, z});
    }

    for(i = 1; i <= n; i++) t[i] = i, lg[i] = 1;
    for(it = a.begin(); it != a.end(); it++)
    {
        x = radacina((*it).x);
        y = radacina((*it).y);

        if(x != y)
        {
            uneste(x, y);
            s += (*it).cost;
            r.push_back({(*it).x, (*it).y});
        }
    }

    fout << s << '\n' << n - 1 << '\n';
    for(itt = r.begin(); itt != r.end(); itt++) fout << (*itt).x << ' ' << (*itt).y << '\n';

    return 0;
}

void uneste(int x, int y)
{
    if(lg[x] < lg[y]) lg[y] += lg[x], t[x] = y;
    else lg[x] += lg[y], t[y] = x;
}

int radacina(int x)
{
    if(t[x] != x) t[x] = radacina(t[x]);

    return t[x];
}