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

#define Edge pair<int, pair<int,int> >
#define cost first
#define x second.first
#define y second.second

const int Nmax = 200001;

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

int N, M, APM_cost;
vector <Edge> E, APM;

int T[Nmax], Sz[Nmax];

int Root(int a) { int R; for (R = a; R != T[R]; R = T[R]); for (int aux; a != T[a]; aux = T[a], T[a] = R, a = aux); return R; }
void Unite(int a, int b) {  if (Sz[a] > Sz[b])  T[b] = a; else    T[a] = b; if (Sz[a] == Sz[b]) Sz[b]++; }

int main()
{
    is >> N >> M;
    E = vector <Edge> (M);
    for (int i = 0; i < M; ++i)
        is >> E[i].x >> E[i].y >> E[i].cost;

    sort(E.begin(), E.end());

    for (int i = 1; i <= N; ++i)
        T[i] = i, Sz[i] = 1;
    for (int i = 0, Rx, Ry; i < M && APM.size() < N-1; ++i)
    {
        Rx = Root(E[i].x);
        Ry = Root(E[i].y);
        if (Rx != Ry)
        {
            Unite(Rx, Ry);
            APM_cost += E[i].cost;
            APM.push_back(E[i]);
        }
    }
    os << APM_cost << '\n' << APM.size() << '\n';
    for (const auto& e : APM)
        os << e.x << ' ' << e.y << '\n';

    is.close();
    os.close();
}