// Lab3.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

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

int n, m;
std::vector<std::vector<int>> G, Arb;
std::vector<int> cc, sz;

void citire()
{
	int x, y, cost;
	in >> n >> m;
	while (in >> x >> y >> cost)
	{
		G.push_back({ cost,x,y });
	}
} 

void uneste(int x, int y) {
	for (int i = 1; i <= n; i++)
	{
		if (cc[i] == y)
			cc[i] = x;
	}
}

int find_set(int v) {
    if (cc[v] == v) return v;
    return cc[v] = find_set(cc[v]);
}

bool union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) std::swap(a, b);
    cc[b] = a;
    sz[a] += sz[b];
    return true;
}


void Kruskal()
{
    int ct = 0;
    int nrm = 0;
    Arb.clear();

    cc.assign(n + 1, 0);        
    for (int i = 1; i <= n; ++i) {
        cc[i] = i;
    }

    std::sort(G.begin(), G.end());
    for (auto muchie : G) {
        int cost = muchie[0], x = muchie[1], y = muchie[2];
        if (cc[x] == cc[y])
        {
            continue;
        }
        if (union_sets(x, y)) {
            ct += cost;
            Arb.push_back(muchie);
            uneste(cc[x], cc[y]);
            nrm++;
            if (nrm == n - 1)
            {
                break;
            }
        }

        out << ct << "\n";
        out << Arb.size() << "\n";
        for (auto& muchie : Arb)
            out << muchie[1] << " " << muchie[2] << "\n";
    }
}

int main(){
    citire();
    Kruskal();
    out.close();
    in.close();
    return 0;
}