#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int n, m, finalCost;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
vector<pair<int, int>> mst;
vector<int> parent(n+1);
int find(int x)
{
    if(parent[x] == x)
        return x;
    return parent[x] = find(parent[x]);
}
void unite(int a, int b)
{
    a = find(a);
    b = find(b);
    if(a != b)
        parent[a] = b;
}
int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in >> n >> m;
    for(int i=0;i<m;i++)
    {
        int a, b, cost;
        in >> a >> b >> cost;
        pq.push({cost, a, b});
    }
    
    for(int i=1;i<=n;i++)
        parent[i] = i;

    while(!pq.empty() && mst.size() < n-1)
    {
        auto [cost, a, b] = pq.top();
        pq.pop();
        if(find(a) != find(b))
        {
            unite(a, b);
            mst.push_back({a, b});
            finalCost += cost;
        }
    }
    out << finalCost << '\n' << mst.size() << '\n';
    for(int i=0;i<mst.size();i++)
        out << mst[i].first << ' ' << mst[i].second << '\n';

    return 0;
}