#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int, pair<int, int>>> c_m; /// cost_muchie
vector<pair<int, int>> arbore;
int Parinte[100001], Rank[100001];

void makeset(int u)
{
    for(int i = 1; i <= u; i++)
    {
        Parinte[i] = i;
        Rank[i] = 0;
    }
}
int find_(int x) /// Gasim parintele nodului
{
    while (x != Parinte[x]) /// Cat timp parintele lui x nu este bunicul (parintele parintelui) sau parintele lui x devine bunicul sau
        x = Parinte[x];     /// Ne oprim cand x = parinte
    return x;
}

void union_(int x, int y)   /// REFACE ASTA PENTRU DIMENSIUNE ARBORE
{
    int r_x = find_(x);
    int r_y = find_(y);
    /*if (Rank[r_x] >= Rank[r_y]) /// Daca rankul parintelui lui x este mai mare decat rankul parintelui lui y, parintele lui x devine parintele lui y
    {
        Parinte[r_y] = r_x;
        Rank[r_x] += Rank[r_y];
    }
    else
    {
        Parinte[r_x] = r_y;
        Rank[r_y] += Rank[r_x]; /// Daca rankul este identic, facem rankul parintelui lui y mai mare ca sa devina parintele arborelui partial
    }*/
    if (Rank[r_x] > Rank[r_y]) /// Daca rankul parintelui lui x este mai mare decat rankul parintelui lui y, parintele lui x devine parintele lui y
    {
        Parinte[r_y] = r_x;
    }
    else
    {
        Parinte[r_x] = r_y;
        if(Rank[r_x] == Rank[r_y]) Rank[r_y] = Rank[r_y] + 1; /// Daca rankul este identic, facem rankul parintelui lui y mai mare ca sa devina parintele arborelui partial
    }
}

void kruskal(int& cost)
{
    sort(c_m.begin(), c_m.end());
    for(auto m : c_m)
    {
        ///cout << m.second.first << " " << m.second.second << " || ";

        if(find_(m.second.first) != find_(m.second.second)) /// Daca cele doua noduri nu apartin aceluiasi arbore partial
        {
            ///cout << find_(m.second.first) << " " << find_(m.second.second) << " = " << m.first << " || ";
            ///cout << endl;
            arbore.push_back({m.second.first, m.second.second});
            union_(m.second.first, m.second.second);
            cost += m.first;
        }
    }
}

int main()
{
    int N, M, cost = 0;
    in >> N >> M;
    makeset(N);
    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        c_m.push_back({c, {x, y}});
    }

    kruskal(cost);
    out << cost << '\n' << arbore.size() << '\n';
    for(int i = 0; i < arbore.size(); i++)
        out << arbore[i].first << " " << arbore[i].second << '\n';
    return 0;
}