//
// Created by Cristian Stern on 5/20/2019.
//
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
struct Edge{
int x, y, cost;
Edge(int a, int b, int weight);
Edge(){}
};
Edge::Edge(int a, int b, int weight) {
x = a;
y = b;
cost = weight;
}
bool cmp(Edge a, Edge b){
return a.cost < b.cost;
}
int find(int x, vector < int > &T){
int R, y;
for(R = x; R != T[R]; R = T[R]);
while(T[x] != R){
y = T[x];
T[x] = R;
x = y;
}
return R;
}
void unite(int x, int y, vector <int> &T, vector < int > &R){
if(R[x] > R[y])
T[y] = x;
else T[x] = y;
if(R[x] == R[y]){
R[y]++;
}
}
int main(){
//ifstream f("E:\\FMI\\AG\\lab3\\date.in");
//ofstream g("E:\\FMI\\AG\\lab3\\date.out");
ifstream f("apm.in");
ofstream g("apm.out");
int n, m;
vector < pair < int, int > > rez;
int x, y, cost;
f>>n>>m;
vector < Edge > G(m);
vector < int > TT(n);
vector < int > RG(n);
for(int i = 0;i < n;i++){
TT[i] = i;
RG[i] = 1;
}
for(int i = 0;i < m;i++){
f>>x>>y>>cost;
x--;
y--;
G.emplace_back(x, y, cost);
}
sort(G.begin(), G.end(), cmp);
int nr = 0;
int s = 0;
for(int i = 0;i < m;i++){
Edge u = G[i];
if(find(u.x, TT) != find(u.y, TT)){
unite(find(u.x, TT), find(u.y, TT), TT, RG);
rez.emplace_back(u.x + 1, u.y + 1);
s += u.cost;
nr++;
/*if(nr == n - 1)
break;*/
}
}
g<<s<<"\n";
g<<n-1<<"\n";
for(auto muchie : rez)
g<<muchie.first<<" "<<muchie.second<<"\n";
}