// Kruskal.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int find(int i, vector<int>& parent)
{
    if (parent[i] == i) return i;
    return parent[i] = find(parent[i], parent);
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;
    f >> n >> m;
    vector<int> parent(n + 1);
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    vector<tuple<int, int, int>> edges(m+1);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        f >> a >> b >> c;
        edges.push_back({ c,a,b });
    }
    sort(edges.begin(), edges.end());
    long long sum = 0;
    vector<pair<int, int>> res;
    for (auto [c, x, y] : edges)
    {
        int px = find(x, parent);
        int py = find(y, parent);
        if (px != py)
        {
            parent[px] = py;
            sum += c;
            res.push_back({ x,y });
        }
    }
    g << sum << endl;
    g << res.size() << endl;
    for (auto x : res)
        g << x.first << " " << x.second << endl;
}