#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Edge{
int first;
int second;
int cost;
bool operator>(const Edge &other) const {
if(cost == other.cost){
if(first == other.first){
return second > other.second;
}
return first > other.first;
}
return cost > other.cost;
}
};
struct Node{
int node;
int cost;
};
int main(){
int n, m, result = 0;
fin >> n >> m;
vector<vector<Node>> adj(n, vector<Node>());
vector<bool> visited(n, false);
for(int i = 0; i < m; i++){
int first_node, second_node, cost;
fin >> first_node >> second_node >> cost;
first_node--;
second_node--;
adj[first_node].push_back({second_node, cost});
adj[second_node].push_back({first_node, cost});
}
visited[0] = true;
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
for(auto it : adj[0]){
int node = it.node;
int cost = it.cost;
pq.push({0, node, cost});
}
vector<pair<int, int>> muchii_arbore;
while(!pq.empty()){
Edge top = pq.top();
pq.pop();
if(visited[top.second] == true){
continue;
}
visited[top.second] = true;
result += top.cost;
muchii_arbore.push_back({top.first + 1, top.second + 1});
for(auto it : adj[top.second]){
if(visited[it.node] == false){
pq.push({top.second, it.node, it.cost});
}
}
}
fout << result << '\n';
fout << n + 1 << '\n';
for(auto it : muchii_arbore){
fout << it.first << " " << it.second << '\n';
}
return 0;
}