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

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

const int NMAX = 200000;

struct muchie
{
    int x, y, cost;
};

struct compara
{
    bool operator() (muchie a, muchie b)
    {
        return a.cost > b.cost;
    }
};


std::priority_queue<muchie, std::vector<muchie>, compara> Q;
std::vector<std::pair<int, int>> G[NMAX];
int rank[NMAX];
int tata[NMAX];
std::vector<muchie>Rez;
//std::queue<std::pair<int, int>> Q;
int N, M;
int Suma_Arbore = 0;

void citire()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        muchie m;
        int x, y, cost;
        fin >> x >> y >> cost;
        G[x].push_back({ y,cost });
        G[y].push_back({ x,cost });
        m.x = x;
        m.y = y;
        m.cost = cost;
        Q.push(m);
    }
}

void test_coada()
{
    while (!Q.empty())
    {
        std::cout << Q.top().x<<" " << Q.top().y <<" "<<Q.top().cost << '\n';
        Q.pop();
    }
}

int find(int nod)
{
    if (tata[nod] == 0)
        return nod;
    else 
        tata[nod] = find(tata[nod]);
}

void unesc(int nod1, int nod2, int cost)
{
    int tata_nod1 = find(nod1);
    int tata_nod2 = find(nod2);
    if (tata_nod1 != tata_nod2)
    {
        if (rank[tata_nod1] > rank[tata_nod2])
            tata[tata_nod2] = tata_nod1;
        else if (rank[tata_nod1] < rank[tata_nod2])
            tata[tata_nod1] = tata_nod2;
        else
        {
            rank[tata_nod1]++;
            tata[tata_nod2] = tata_nod1;
        }
        muchie m;
        m.x = nod1;
        m.y = nod2;
        m.cost = cost;
        Rez.push_back(m);
        Suma_Arbore += cost;
    }
}

void Kruskal()
{
    while (!Q.empty())
    {
        muchie muchie_ieftina = Q.top();
        Q.pop();
        unesc(muchie_ieftina.x, muchie_ieftina.y, muchie_ieftina.cost);
    }

    fout << Suma_Arbore << '\n';
    fout << Rez.size() << '\n';
    for (auto m : Rez)
    {
        fout << m.x << " " << m.y << '\n';
    }
}

int main()
{
    citire();
    //test_coada();
    Kruskal();
}