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

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

vector<vector<int>> edges; 
vector<int> r;
int cost;
vector<vector<int>> output;

void initEdges(int &n, int &m)
{
    edges.resize(m); 
    for (int i = 0; i < m; i++)
    {
        int x, y, c; 
        f >> x >> y >> c; 
        edges[i] = {c, x, y}; 
    }
}

void sorteaza()
{
    sort(edges.begin(), edges.end()); 
}

// Functia Init initializeaza reprezentantul unui nod u cu el insusi
void Init(int u)
{
    r[u] = u; 
}

// Functia Reprez gaseste reprezentantul unui nod u
// Daca nodul u nu este reprezentantul lui insusi, atunci se apeleaza recursiv pentru a gasi reprezentantul
int Reprez(int u)
{
    if (r[u] != u) {
        r[u] = Reprez(r[u]); // Path compression pentru a optimiza timpul de executie
    }
    return r[u];
}

// Functia Reuneste uneste doua componente conexe reprezentate de nodurile u si v
void Reuneste(int u, int v)
{
    int r1 = Reprez(u); // Gaseste reprezentantul lui u
    int r2 = Reprez(v); // Gaseste reprezentantul lui v
    if (r1 != r2) { 
        r[r2] = r1; // Uneste cele doua componente conexe, facand ca r2 sa fie subordonat lui r1
    }
}

// Algoritmul lui Kruskal pentru a gasi arborele partial de cost minim
void kruskal(int n)
{
    // Initializarea reprezentantilor pentru fiecare nod
    for (int v = 1; v <= n; v++)
        Init(v); 
    // Sortarea muchiilor dupa greutate
    sorteaza(); 
    // Parcurgerea muchiilor si unirea nodurilor
    for (int i = 0; i < edges.size(); i++)
    {
        int c = edges[i][0]; 
        int x = edges[i][1]; 
        int y = edges[i][2]; 
        // Verificarea daca muchia nu formeaza un ciclu
        if (Reprez(x) != Reprez(y)) 
        {
            // Unirea nodurilor
            Reuneste(x, y); 
            // Afisarea muchiei selectate
            output.push_back({y, x});
            cost += c; 
        }
    }
}

int main()
{
    int n, m; 
    f >> n >> m; 
    r.resize(n + 1); 
    initEdges(n, m); 
    kruskal(n); 
    g << cost << endl;
    g << output.size() << endl;
    for (auto edge : output) {
        g << edge[0] << " " << edge[1] << endl;
    }

    f.close(); 
    g.close();
    return 0;
}