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

using namespace std;

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

struct muchie{
    int n1;
    int n2;
    int cost;
    muchie(int n1, int n2, int cost):n1(n1),n2(n2),cost(cost){}
};

int main()
{
    int n,m,s,f,v,cost_total = 0;

    vector<muchie> muchii;
    vector<muchie> finale;
    int colorare[200001];

    in>>n>>m;

    for (int i = 0; i < m; i++)
    {
        in>>s>>f>>v;

        muchii.push_back(muchie(s,f,v));
    }

    for (int i = 0 ; i<m; i++)
        for (int j = i + 1; j < m; j++)
            if (muchii[j].cost < muchii[i].cost)
                swap(muchii[i], muchii[j]);

    for (int i = 1; i <= n; i++) colorare[i] = i;

    for (int i = 0; i < m; i++)
        if (colorare[muchii[i].n1] != colorare[muchii[i].n2])
        {
            colorare[muchii[i].n1] = colorare[muchii[i].n2];

            finale.push_back(muchii[i]);

            cost_total += muchii[i].cost;
        }

    out<<cost_total<<"\n"<<finale.size()<<"\n";

    for (int i = 0; i < finale.size(); i++) out<<finale[i].n1<<" "<<finale[i].n2<<"\n";

    return 0;
}