#include <fstream>
#include <iostream>
#include <queue>
using namespace std;

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

class muchie
{
public:
    int cost, to, from;
    // When true is returned, it means the order is correct and NO swapping of elements takes place.
    // When false is returned, it means the order is NOT correct and swapping of elements takes place.
    bool operator<(const muchie &above) const
    {
        return cost > above.cost;
    }
};

vector<muchie> G[200005];
vector<int> capete_muchie[200005];
priority_queue<muchie> min_heap;
long long N, M, cost_total, nr_muchii;
bool vizitat[200005];

void minSpanningTree()
{
    muchie root;
    root.cost = 0;
    root.to = 1;
    root.from = 0;
    min_heap.push(root);
    while (!min_heap.empty())
    {
        while (!min_heap.empty() && vizitat[min_heap.top().to])
            min_heap.pop();
        if (min_heap.empty())
            break;
        muchie muchie_curenta = min_heap.top();
        nr_muchii++;
        capete_muchie[muchie_curenta.from].push_back(muchie_curenta.to);
        min_heap.pop();
        cost_total += muchie_curenta.cost;
        vizitat[muchie_curenta.to] = true;
        for (int i = 0; i < G[muchie_curenta.to].size(); i++)
        {
            muchie nod_nou;
            nod_nou.cost = G[muchie_curenta.to][i].cost;
            nod_nou.to = G[muchie_curenta.to][i].to;
            nod_nou.from = muchie_curenta.to;
            min_heap.push(nod_nou);
        }
    }
}

// Algoritmul lui Kruskal

int main()
{
    int X, Y, C;
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        fin >> X >> Y >> C;
        muchie it;
        it.cost = C;
        it.to = Y;
        G[X].push_back(it);
        it.to = X;
        G[Y].push_back(it);
    }
    minSpanningTree();
    fout << cost_total << "\n"
         << nr_muchii - 1 << "\n";
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j < capete_muchie[i].size(); j++)
            fout << i << " " << capete_muchie[i][j] << "\n";
    }
    return 0;
}