#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int NMAX = 1e5 * 4;
int n, m;
int root[NMAX / 2 + 5];
int rang[NMAX / 2 + 5];
int cost_arb;
vector<pair<int, int> > ans;

void init_multimi()
{
    for(int i = 1; i <= n; ++i)
    {
        root[i] = i;
        rang[i] = 1;
    }
}

int Find(int node)
{
    if(node != root[node])
    {
        root[node] = Find(root[node]);
    }

    return root[node];
}

void unite(int root1, int root2)
{
    if(root1 != root2)
    {
        if(rang[root1] < rang[root2])
        {
            swap(root1, root2);
        }

        root[root2] = root1;
        rang[root1] += rang[root2];
    }
}

struct vertex
{
    int node1;
    int node2;
    int cost;
};
vector<vertex> muchii;

bool comp(vertex a, vertex b)
{
    return a.cost < b.cost;
}


void apm()
{
    for(int i = 0; i < m; ++i)
    {

        int x = muchii[i].node1;
        int y = muchii[i].node2;
        int c = muchii[i].cost;

        if(Find(x) == Find(y))
            continue;

        cost_arb += c;
        unite(Find(x), Find(y));

        ans.push_back({x, y});
    }
}

int main()
{
    in >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        int u, v, c;

        in >> u >> v >> c;

        muchii.push_back({u, v, c});
    }

    sort(muchii.begin(), muchii.end(), comp);

    init_multimi();

    apm();

    out << cost_arb << '\n' << ans.size() << '\n';

    for(auto m : ans)
    {
        out << m.first << ' ' << m.second << '\n';
    }

    return 0;
}