/**
  * Algoritmul lui Prim - graf neorientat
  */

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

#define INPUT_FILE_NAME "apm.in"
#define OUTPUT_FILE_NAME "apm.out"
#define N_MAX 200000
#define PII std::pair< int, int >

struct Muchie {

	int dest, cost;
	Muchie (int _dest, int _cost) {
        dest = _dest;
        cost = _cost;
    }

};

struct Graf {

	int n, m;
	std::vector <Muchie> a[N_MAX];

};

void read_file (Graf &g) {
	
	std::fstream fin (INPUT_FILE_NAME, std::ios::in);
	fin >> g.n >> g.m;
	int src, dest, cost;
	while (fin >> src >> dest >> cost) {
		g.a[src].push_back (Muchie (dest, cost));
		g.a[dest].push_back (Muchie (src, cost));
	}
	fin.close ();
}

void print_graf (Graf &g) {
	
	std::cout << "N = "<< g.n << " M = " << g.m << '\n';
	for (int i = 1; i <= g.n; i++) {
		std::cout << i << ": ";
		for (std::vector<Muchie>::iterator it = g.a[i].begin(); it != g.a[i].end(); it++) {
			std::cout << it->dest << " (cost " << it->cost << "); ";
		}
		std::cout << '\n';
	}
}

struct compare {
	bool operator()(PII const & l, PII const & r) {
		return l.second > r.second;
  }
}; 

void print_ama (std::vector <PII> &ama, int &ama_cost) {
	
	std::cout << "Cost ama " << ama_cost << "\n";
  	for (unsigned int i = 0; i < ama.size(); i++) {
  		std::cout << ama[i].first << " - " << ama[i].second << "\n";
  	}
  	std::cout << "\n";

}

void print_queue (std::priority_queue < PII, std::vector < PII >, compare> pq) {

 	while (!pq.empty()) {
  		std::cout << "(" << pq.top().first << "-" << pq.top().second<< ") ";
  		pq.pop();
  	}

  	std::cout << "\n";

}

int get_cost (Graf &g, int x, int y) {

	for (unsigned int i = 0; i < g.a[x].size(); i++) {
		if (g.a[x][i].dest == y) {
			return g.a[x][i].cost;
  		}
  	}

  	return 0;

}

void prim (Graf &g, int s, std::vector <PII> &ama, int &ama_cost) {
	
	int d[1000], p[1000];
	bool in_ama [1000];
	std::priority_queue < PII, std::vector < PII >, compare > pq; 
  	
  	for (unsigned int i = 1; i <= g.n; i++) {
  		d[i] = INT_MAX;
  		p[i] = 0;
  	}

  	d[s] = 0;
  	pq.push (PII (s, d[s]));
	int u = -1;
  
  	while (!pq.empty()) {

        //std::cout << "Coada initiala : ";
        //print_queue (pq);

    	// caut primul nod (la departare minima de ama) care nu este in ama
    	do {

    		u = pq.top().first;
    		pq.pop();
    
    	} while (!pq.empty() && in_ama[u] == true);
        if (pq.empty() && in_ama[u] == true)
            break;

        //std::cout << "Aleg " << u << "\n";

    	// il introduc in ama si-l marchez   
    	ama.push_back (std::make_pair (u, p[u]));
    	in_ama [u] = true;

		for (std::vector<Muchie>::iterator it = g.a[u].begin(); it != g.a[u].end(); it++) {
			if (it->cost < d[it->dest]) {

        		d[it->dest] = it->cost;
       			p[it->dest] = u;
        		pq.push(std::pair <int, int> (it->dest, d[it->dest]));

      		}
    	}

        //std::cout << "Coada finala : ";
        //print_queue (pq);
        //std::cout << "--------------------------------\n";


    }

	// sterg din ama perechea (sursa, 0)
	std::vector< PII >::iterator it;
  	it = std::find (ama.begin(), ama.end(), std::make_pair (s, 0));
  	if (it != ama.end())
  	  	ama.erase (it);

  	for (std::vector<PII>::iterator it = ama.begin(); it < ama.end(); it++) {
    
    	ama_cost = ama_cost + get_cost(g, it->first, it->second);
    
    }

}

int main(void) {
	
	Graf g;
	read_file(g);
//	print_graf(g);

	std::vector <PII> ama;
	int ama_cost = 0;
	prim (g, 1, ama, ama_cost);
	//print_ama (ama, ama_cost);

    std::fstream fout (OUTPUT_FILE_NAME, std::ios::out);
    fout << ama_cost << "\n" << ama.size() << "\n";
    for (unsigned int i = 0; i < ama.size(); i++) {
        fout << ama[i].first << " " << ama[i].second << "\n";
    }
    fout.close();

	return 0;
}