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

using namespace std;

int n, m, costTotal;
vector<vector<int>> muchii;
vector<int> tata;
vector<int> solutie;

void citire()
{
    ifstream f("apm.in");

    f >> n >> m;

    tata.resize(n + 1);

    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        f >> x >> y >> c;
        muchii.push_back({x, y, c});
    }

    sort(muchii.begin(), muchii.end(), [](vector<int> a, vector<int> b) {return a[2] < b[2];});
}

int getRoot(int nod)
{
    while(tata[nod] != nod)
        nod = tata[nod];
    return nod;
}

void determinareSolutie()
{
    for(int nod = 1; nod <= n; nod++)
        tata[nod] = nod;

    int indexMuchie = 0;
    for(auto muchie : muchii)
    {
        int nod1 = muchie[0];
        int nod2 = muchie[1];
        int cost = muchie[2];

        int root1 = getRoot(nod1);
        int root2 = getRoot(nod2);

        if(root1 != root2)
        {
            solutie.push_back(indexMuchie);
            costTotal += cost;   
        
            tata[root1] = root2;
        }

        indexMuchie++;
    }
}

void afisare()
{
    ofstream g("apm.out");
    g << costTotal<< endl;
    g << solutie.size() << endl;
    for(int i = 0; i < solutie.size(); i++)
    {
        int index = solutie[i];

        g << muchii[index][0] << ' ' << muchii[index][1] << endl;
    }
}

int main()
{
    citire();
    determinareSolutie();
    afisare();

    return 0;
}


/**
 * Kruskal Algorithm and Prim Algorithm
 * 
 * 
*/