#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector <pair<int, int>> ed;
int tcost;

int find(vector <int> & par, int x) {
	if (x != par[x])
		par[x] = find(par, par[x]);
		
	return par[x];
} 

void unite(vector <int> & par, vector <int> & sz, int x, int y, int c) {
	int pax = find(par, x);
	int pay = find(par, y);
	
	//cout <<x<<" "<<y<<endl;
	if (pax == pay)
		return;
	
	ed.push_back(make_pair(x, y));
	tcost += c;
	
	if (sz[pax] < sz[pay]){
		swap(x, y);
		swap(pax, pay);
	}
	
	par[y] = par[pay] = pax;
	sz[pax] += sz[pay]; 
}

int main() {
    int n, m, x, y, c;
    long long sum;
       
    ifstream myfile;
    myfile.open ("apm.in");
    myfile>>n>>m;
    //cout <<n<<" "<<m<<endl;
    vector <pair<int, int>> cost(m), nod(m);
    vector <int> par(n), sz(n, 1);
    
    for (int i = 0; i < m; i++) {
        myfile>>x>>y>>c;
        cost[i] = make_pair(c, i);
        nod[i] = make_pair(x, y);
    }
    myfile.close();
    
    for (int i = 0; i < n; i++)
    	par[i] = i;	
    	
    tcost = 0;
    
    sort(cost.begin(), cost.end());
    
    for (auto pa: cost) {
    	int j = pa.second;
    	//unite(par, sz, nod[j].first, nod[j].second, pa.first);
    }
    
    ofstream f2;
    f2.open ("apm.out");
    f2<<tcost<<endl;
    f2<<ed.size()<<endl; 
     for (auto pa: ed) {
        f2<<pa.first<<" "<<pa.second<<endl;
     }
     
    f2.close();
       
    return 0;
}