#include <bits/stdc++.h>
#include <limits>

using namespace std;

int infinit = std::numeric_limits<int>::max();

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

vector<pair<int, pair<int, int>>> c_m; /// cost_muchie
vector<pair<int, int>> arbore;
int P[100001], R[100001];

void makeset(int u)
{
    for(int i = 1; i <= u; i++)
    {
        P[i] = i;
        R[i] = 0;
    }
}
int find_(int x)
{
    while (x != P[x])
        x = P[x];
    return x;
}

void union_(int x, int y)
{
    int r_x = find_(x);
    int r_y = find_(y);
    if (R[r_x] > R[r_y])
    {
        P[r_y] = r_x;
    }
    else
    {
        P[r_x] = r_y;
        if(R[r_x] == R[r_y]) R[r_y] = R[r_y] + 1;
    }
}

void kruskal(int& cost)
{

    sort(c_m.begin(), c_m.end());
    for(auto m : c_m)
    {
        cout << m.second.first << " " << m.second.second << " || ";
        cout << find_(m.second.first) << " " << find_(m.second.second) << " || ";

        cout << endl;
        if(find_(m.second.first) != find_(m.second.second))
        {
            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;
}