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

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

const int nmax = 2e5 + 2;
struct edge{int x, y, cost;};
vector <edge> edges;

///kruskall   - cu dsu
struct DSU {
    vector<int> comp, sz;

    DSU (int n)
    {
        comp.resize(n + 1);
        sz.resize(n + 1, 1);
        for (int i = 1; i <= n; i++)
        {
            comp[i] = i;
        }
    }

    int find (int x)
    {
        if (comp[x] == x) return x;
        else return comp[x] = find(comp[x]);
    }

    void unite(int x, int y)
    {
        x = find(x), y = find(y);
        if (sz[x] < sz[y]) swap(x, y);
        if (x == y) return;
        comp[y] = x;
        sz[x] += sz[y];
    }
};

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



int main()
{
    int n, m, x, y, cost;
    ll cf;
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        cin >> x >> y >> cost;
        edges.push_back({x, y, cost});
    }
    DSU dsu(n);
    vector<pair<int, int>> rasp;
    sort(edges.begin(), edges.end(), comp);
    for(int i = 0; i < edges.size(); ++i){
        if(dsu.find(edges[i].x) != dsu.find(edges[i].y)){
            dsu.unite(edges[i].x, edges[i].y);
            cf += edges[i].cf;
            rasp.push_back({edges[i].x, edges[i].y});
        }
    }
    cout << cost << '\n' << rasp.size() << '\n';
    for(int i = 0; i < rasp.size(); ++i)
        cout << rasp[i].second << ' ' << rasp[i].first << '\n';
    return 0;
}