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

using namespace std;

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

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

bool compare(const edge &a, const edge &b)
{
    return a.cost < b.cost;
}

int find(int x, vector<int> &parent)
{
    if(parent[x] != x)
    {
        parent[x] = find(parent[x], parent);
    }

    return parent[x];
}

void merge(int x, int y, vector<int> &parent, vector<int> &rank)
{
    if(x == y) return;

    if(rank[x] < rank[y]) swap(x, y);

    parent[y] = x;

    if(rank[x] == rank[y]) rank[x]++;
}


int main()
{
    int n, m;
    be >> n >> m;

    vector<edge> v(m);

    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        be >> x >> y >> c;

        v[i] = {x, y, c};
    }

    sort(v.begin(), v.end(), compare);

    vector<int> parent(n + 1);
    vector<int> rank(n + 1);

    for(int i = 1; i <= n; i++)
    {
        parent[i] = i;
        rank[i] = 0;
    }

    vector<pair<int, int>> ans;
    int sum = 0;

    for(edge e : v)
    {
        int eu = find(e.x, parent);
        int ev = find(e.y, parent);

        if(eu != ev)
        {
            ans.push_back({e.x, e.y});
            sum += e.cost;

            merge(eu, ev, parent, rank);
        }
    }

    ki << sum << "\n" << ans.size() << "\n";

    for(pair<int, int> p : ans)
    {
        ki << p.first << " " << p.second << "\n";
    }

    return 0;
}