//We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people,
//and they should not go into the same group.
//Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi,
//return true if it is possible to split everyone into two groups in this way.
// Mai pe scurt acesta este un BFS putin diferit
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 2001;
//int n, m;
//bool isBipartite;
//int adj[MAX][MAX], viz[MAX];
//queue<int> q;
//
//void BFS(){
// q.push(1);
// viz[1] = 1;
// while(!q.empty()){
// int aux = q.front();
// q.pop();
// for(int i = 1; i <= n; i++){
// if(viz[aux] == viz[i] && adj[aux][i] == 1){
// isBipartite = false;
// return;
// }
// else if(adj[aux][i] == 1 && viz[i] == 0){
// q.push(i);
// if(viz[aux] == 1){
// viz[i] = 2;
// }
// else{
// viz[i] = 1;
// }
// }
// }
// }
//}
//
//int main() {
//
// fin >> n >> m;
// for(int i = 1; i <= m; i++){
// int x, y;
// fin >> x >> y;
// adj[x][y] = adj[y][x] = 1;
// }
// isBipartite = true;
// BFS();
// if(!isBipartite){
// fout << "False" << endl;
// }
// else{
// fout << "True" << endl;
// for(int i = 1; i <= n; i++){
// if(viz[i] == 1){
// fout << i << ' ';
// }
// }
// fout<<endl;
// for(int i = 1; i <= n; i++){
// if(viz[i] == 2){
// fout << i << ' ';
// }
// }
// fout<<endl;
// }
//
// return 0;
//}
//
//One of the most popular algorithms for traversing a graph is the Depth First Search (DFS).
//The DFS is usually implemented as a recursive function. First we call the function for the starting node.
//For each call, we go through the adjacency list of the current node, and recursively call the function for the unvisited neighbours.
//Notice that if we permute the adjacency lists of the nodes, the order in which we visit them might differ.
//In this problem you are given a graph with N nodes and M edges and a permutation P of size N.
//If you are allowed to shuffle the adjacency lists, is it possible to visit the nodes during a DFS starting in node
//1 in the order given by P?
//Mai pe scurt acesta este un DFS care are o sortare in fiecare lista de adiacenta!
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 1e5 + 3;
//int n, m;
//vector<int> adj[MAX], dfs_order;
//int ord[MAX], viz[MAX];
//
//
//int compara(int a, int b){
// return ord[a] < ord[b];
//}
//
//void DFS(int node){
// viz[node] = 1;
// dfs_order.push_back(node);
// for(auto vecin : adj[node]){
// if(viz[vecin] == 0){
// DFS(vecin);
// }
// }
//}
//
//int main() {
//
// fin >> n >> m;
// vector<int> permutare(n);
// for(int i = 1; i <= n; i++){
// int aux;
// fin >> aux;
// ord[aux] = i;
// permutare[i - 1] = aux;
// }
//
//
// for(int i = 1; i <= m; i++){
// int x, y;
// fin >> x >> y;
// adj[x].push_back(y);
// adj[y].push_back(x);
// }
// for(int i = 1; i <= n; i++){
// sort(adj[i].begin(), adj[i].end(), compara);
// }
//
// DFS(1);
// // fout << "dfs_order : " << endl;
// // for(int i = 0; i < n ; i++){
// // fout << dfs_order[i] << ' ';
// // }
// // fout << endl << "permutare : \n";
// // for(int i = 0; i < n; i++){
// // fout << permutare[i] << ' ';
// // }
// fout << (permutare == dfs_order) << endl;
//
// return 0;
//}
//There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where
//prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
//For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
//Return the ordering of courses you should take to finish all courses. If there are many valid answers,
//return any of them. If it is impossible to finish all courses, return an empty array.
//
//Problema cu cursurile adica un graf orientat in care trebuie sa aflam daca avem ciclu sau nu. Nu e terminata aici.
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//const int MAX = 1e4 + 1;
//int n, m;
//vector<int> adj[MAX], viz, cur_path, rezultat;
//vector<int> DFS(int node){
//
// if(viz[node]){
// return {};
// }
// if(cur_path[node]){
// return {node};
// }
//
// viz[node] = 1;
// cur_path[node] = 1;
// for(auto vecin : adj[node]){
// vector<int> ciclu = DFS(vecin);
// if(!ciclu.empty()){
// return ciclu;
// }
// }
// cur_path[node] = 0;
// rezultat.push_back(node);
// return {};
//}
//
//int main() {
// fin >> n >> m;
// for(int i = 1; i <= m; i++){
// int x, y;
// fin >> x >> y;
// adj[y].push_back(x);
// }
// int ans = 1;
// for(int i = 1; i <= n; i++){
// if(!viz[i]){
// vector<int> ciclu = DFS(i);
// if(!ciclu.empty()){
// ans = 0;
// }
// }
// }
//
//
// return 0;
//}
//Componente tare conexe
// Se dă un graf orientat G = (V, E). O componentă tare conexă a grafului orientat G este o mulţime maximală de vârfuri U inclusă în V,
// astfel încât, pentru fiecare pereche de vârfuri u şi v din U avem atât drum de la u la v cât şi drum de la v la u. Cu alte cuvinte,
// vâfurile u şi v sunt accesibile unul din celălalt.
//
//Cerinţă
// Dându-se un graf orientat G = (V, E) se cere să se determine componentele sale tare conexe.
//
//Date de intrare
// Fişierul de intrare ctc.in conţine pe prima linie două numere naturale N si M ce reprezintă numărul de noduri din G şi
// numărul muchiilor. Pe următoarele M linii se vor afla câte două numere naturale x şi y, separate prin spaţiu, reprezentând muchia orientată (x, y).
//
//Date de ieşire
// În fişierul de ieşire ctc.out se va afişa pe prima linie un singur număr reprezentând numărul componentelor tare conexe.
// Pe fiecare din următoarele linii se va scrie câte o componentă tare conexă prin enumerarea nodurilor componente.
// Acestea pot fi afişate în orice ordine.
//
//
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("ctc.in");
//ofstream fout("ctc.out");
//
//const int MAX = 1e5 + 1, NEVIZITAT = -1;
//
//int n, m, id, sccCount, ids[MAX], low[MAX];
//vector<int> adj[MAX], cur_path[MAX];
//stack<int> stiva;
//vector<bool> onStack(MAX, false);
//
//
//void DFS(int node){
//
// onStack[node] = true;
// stiva.push(node);
// ids[node] = low[node] = id++;
//
// for(auto vecin : adj[node]){
// if(ids[vecin] == NEVIZITAT){
// DFS(vecin);
// }
//
// if(onStack[vecin]){
// low[node] = min(low[node], low[vecin]);
// }
// }
//
// if(low[node] == ids[node]){
// while(!stiva.empty()){
// int aux = stiva.top();
// stiva.pop();
// cur_path[sccCount].push_back(aux);
// onStack[aux] = false;
// low[aux] = ids[node];
// if(aux == node){
// break;
// }
// }
// sccCount++;
// }
//
//
//}
//
//
//int main() {
//
// fin >> n >> m;
// for(int i = 1; i <= m; i++){
// int x, y;
// fin >> x >> y;
// adj[x].push_back(y);
// }
//
// for(int i = 1; i <= n; i++){
// ids[i] = NEVIZITAT;
// }
//
// for(int i = 1; i <= n; i++){
// if(ids[i] == NEVIZITAT){
// DFS(i);
// }
// }
//
// fout << sccCount << endl;
// for(int i = 0 ; i < sccCount; i++){
// for(auto cmp : cur_path[i]){
// fout << cmp << ' ';
// }
// fout << endl;
// }
// return 0;
//}
//5. Se dă o rețea neorientată cu n noduri și o listă de noduri reprezentând puncte de control pentru
//rețea în fișierul graf.in, în formatul precizat la începutul laboratorului; în plus, pe ultima linie din
//fișier se află punctele de control separate prin spațiu. Să se determine pentru fiecare nod din rețea
//distanța până la cel mai apropiat punct de control de acesta. În fișierul graf.out se vor afișa pentru
//fiecare nod de la 1 la n aceste distanțe separate prin spațiu.
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 1e5 + 1;
//int n, m, control, viz[MAX], dist[MAX];
//vector<int> adj[MAX];
//queue<int> q;
//
//
//void BFS(int node){
// q.push(node);
// viz[node] = 1;
// dist[node] = 0;
//
// while(!q.empty()){
// int nod = q.front();
//
// q.pop();
// for(auto vecin : adj[nod]){
// if(!viz[vecin]){
// q.push(vecin);
// if(dist[vecin] > dist[nod] + 1 && dist[vecin] != 0){
// dist[vecin] = dist[nod] + 1;
// }
// viz[vecin] = 1;
// }
// }
// }
//}
//
//
//int main() {
//
// fin >> n >> m;
// for(int i = 1; i <= m; i++){
// int x, y;
// fin >> x >> y;
// adj[x].push_back(y);
// adj[y].push_back(x);
// }
// fin >> control;
//
// for(int i = 1; i <= n; i++) {
// dist[i] = MAX;
// }
// for(int i = 1; i <= control; i++){
// int pct;
// fin >> pct;
// for(int i = 1; i <= n; i++){
// viz[i] = 0;
// }
// BFS(pct);
// }
// for(int i = 1; i <= n; i++){
// fout << dist[i] << ' ';
// }
//
// return 0;
//}
// In cazul in care am nevoie de sort adj cu pair
//vector<pair<int, int>> adj[10001];
//
////...
//
//// Sortează vectorul de perechi la indexul x în funcție de cost (al doilea element al perechii)
//sort(adj[x].begin(), adj[x].end(), [](const pair<int, int>& a, const pair<int, int>& b) {
//return a.second < b.second;
//});
#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int MAX = 2e5 + 1;
int n, m, tata[MAX], inaltime[MAX], ok;
pair<int, int> final[MAX];
struct muchie{
int x, y, cost;
}adj[2 * MAX];
bool compara(muchie a, muchie b){
return a.cost < b.cost;
}
int cauta(int a){
if(tata[a] == a){
return a;
}
return cauta(tata[a]);
}
void uneste(int a, int b){
int nod1 = cauta(a);
int nod2 = cauta(b);
if(nod1 != nod2){
if(inaltime[nod1] > inaltime[nod2]){
tata[nod2] = nod1;
}
else if(inaltime[nod2] > inaltime[nod1]){
tata[nod1] = nod2;
}
else{
tata[nod1] = nod2;
inaltime[nod2]++;
}
}
}
int main() {
fin >> n >> m;
for(int i = 1; i <= m; i++){
fin >> adj[i].x >> adj[i].y >> adj[i].cost;
}
sort(adj + 1, adj + m + 1, compara);
for(int i = 1; i <= n; i++){
tata[i] = i;
inaltime[i] = 1;
}
int sum = 0;
for(int i = 1; i <= m; i++){
int nod1 = cauta(adj[i].x);
int nod2 = cauta(adj[i].y);
if(nod2 != nod1){
uneste(nod1, nod2);
final[++ok].first = adj[i].x;
final[ok].second = adj[i].y;
sum += adj[i].cost;
}
}
fout << sum << endl;
fout << ok << endl;
for(int i = 1; i <= ok; i++){
fout << final[i].first << ' ' << final[i].second << endl;
}
return 0;
}