#include <iostream>
#include <fstream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int n, m, tc;
vector<pair<int, pair<int,int> > > L;
vector <pair<int,int> >sol;
ifstream in("apm.in");
ofstream out("apm.out");
int p[200001], r[200001];

int find_set(int x){
    if(p[x] != x) p[x] = find_set(p[x]);
    return p[x];
}

void union_set(int x, int y){
    if(r[x] > r[y]) p[y] = x;
    else if(r[y] > r[x]) p[x] = y;
    else{
        p[x] = y;
        r[y] += 1;
    }
}

int main()
{
    in >> n >> m;
    int x, y, c;
    for(int i = 0; i < m; i++) {
        in >> x >> y >> c;
        L.push_back(make_pair(c,make_pair(x,y)));
    }
    sort(L.begin(),L.end());
    //for(int i = 0; i < m; i++) cout << L[i].second.first << " " << L[i].second.second << " " << L[i].first << "\n";
    for(int i = 1; i <= n; i++) {
        p[i] = i; r[i] = 0;
    }
    tc = 0;
    for(int i = 0; i < m; i++){
        x = L[i].second.first; y = L[i].second.second; c = L[i].first;

        int xroot = find_set(x), yroot = find_set(y);

        if(xroot != yroot){
            tc = tc + c;
            union_set(xroot,yroot);
            sol.push_back(make_pair(x,y));
        }
    }
    out << tc << "\n" << n - 1 << "\n;
    for(int i = 0; i < n - 1; i++) out << sol[i].first << " " << sol[i].second << "\n";
    return 0;
}