#include <set>
#include <vector>
#include <fstream>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
vector<pair<int, int> > edges[200000];
set<pair<short int, pair<int, int> > > cost;
set<pair<short int, pair<int, int> > >::iterator iters[200000];
set<int> v;
int main() {
    int n, m;
    long long int cost1 = 0;
    cin>>n>>m;
    for(int x = 0; x<n; x++) {
        v.insert(x);
        iters[x] = cost.insert({10000, {x, -1}}).first;
    }
    vector<pair<int, int> > apm;
    for(int x = 0; x<m; x++) {
        int a, b, c;
        cin>>a>>b>>c;
        edges[a-1].push_back({b-1, c});
        edges[b-1].push_back({a-1, c});
    }
    while(v.size()) {
        auto tmp = *cost.begin();
        cost.erase(cost.begin());
        v.erase(tmp.second.first);
        if(tmp.second.second != -1) {
            apm.push_back(tmp.second);
            cost1 += tmp.first;
        }
        for(pair<int, int> edge : edges[tmp.second.first]) {
            if((v.find(edge.first) != v.end()) && (iters[edge.first]->first > edge.second)) {
                cost.erase(iters[edge.first]);
                iters[edge.first] = cost.insert({edge.second, {edge.first, tmp.second.first}}).first;
            }
        }
    }
    cout<<cost1<<'\n'<<apm.size()<<'\n';
    for(pair<int, int> z : apm) {
        cout<<z.first+1<<' '<<z.second+1<<'\n';
    }
    return 0;
}