/// boruvka
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5+2;
const int INF = 1e6;
using pii = pair<int, int>;
int n,m;
vector<tuple<int, int, int>> edges;

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

struct DSU {
    int n;
    vector<int> t, sz;
    DSU(int _n){
        n = _n;
        t.resize(n+1);
        sz.resize(n+1, 1);
        for(int i = 1; i <= n; i++){
            t[i] = i;
        }
    }
    int root(int nod){
        if(t[nod] == nod){
            return nod;
        }
        return t[nod] = root(t[nod]);
    }
    void join(int x, int y){
        x = root(x);
        y = root(y);
        if(x == y){
            return;
        }
        if(sz[x] < sz[y]){
            swap(x, y);
        }
        sz[x] += sz[y];
        t[y] = x;
    }
    bool areJoined(int x, int y){
        return root(x) == root(y);
    }
};

void chmin(auto &a, auto b){
    a = min(a, b);
}

int main()
{
    fin >> n >> m;
    edges.resize(m);
    for(auto &[x, y, c]: edges){
        fin >> x >> y >> c;
    }
    int ans = 0;
    DSU ds(n);
    vector<pii> apm;
    while(ds.sz[ds.root(1)] != n){
        vector<pii> dist;
        dist.resize(n+1, {INF, -1});
        for(auto [x, y, c]: edges){
            if(!ds.areJoined(x, y)){
                x = ds.root(x);
                y = ds.root(y);
                chmin(dist[x], (pii){c, y});
                chmin(dist[y], (pii){c, x});
            }
        }
        for(int i = 1; i <= n; i++){
            if(dist[i].first != INF && !ds.areJoined(i, dist[i].second)){
                ds.join(i, dist[i].second);
                ans += dist[i].first;
                apm.push_back({i, dist[i].second});
            }
        }
    }
    fout << ans << "\n" << apm.size() << "\n";
    for(auto [x, y]: apm){
        fout << x << " " << y << "\n";
    }
    return 0;
}