#include <bits/stdc++.h>
using namespace std;

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

pair <int, pair<int, int>> c[400001];
int father[200001], h[200001];
pair<int,int> ans[400001];

int opfather(int node)
{
    int root = node;
    while(root != father[root]) root = father[root];
    while(node != root)
    {
        int nextnode = father[node];
        father[node] = root;
        node = nextnode;
    }
    return root;
}

void unire(int x, int y)
{
    int fatherx = opfather(x), fathery = opfather(y);
    if(fatherx == fathery)
        return;
    if(h[fatherx] > h[fathery])
        father[fathery] = fatherx;
    else if(h[fatherx] < h[fathery])
        father[fatherx] = fathery;
    else{
        father[fathery] = fatherx;
        h[fatherx] += 1;
    }
}

int main() {
    int n, m, totalcost = 0;
    fin >> n >> m;
    for(int i = 1; i<= n; ++i)
    {
        father[i] = i;
        h[i] += 1;
    }
    for(int i = 1;i <= m; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        c[i] = {cost, {x, y}};
    }
    sort(c + 1,c + m + 1);
    int k = 0;
    for(int i = 1;i <= m; ++i)
    {
        if(opfather(c[i].second.first) == opfather(c[i].second.second))
            continue;
        totalcost += c[i].first;
        ans[++k] = {c[i].second.first, c[i].second.second};
        unire(c[i].second.first, c[i].second.second);
    }
    cout << totalcost << "\n";
    cout << k << "\n";
    for(int i = 1;i <= k; ++i)
        cout<< ans[i].first << " " << ans[i].second << "\n";
    return 0;
}