#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int parent[200001], sz[200001], n, m;
vector<pair<int, int>> sol;
struct muchi{
int u, v, c;
};
muchi v[400001];
bool operator<(muchi a, muchi b){
return a.c < b.c;
}
void init(){
for(int i = 1;i<=n;i++){
sz[i] = 1;
parent[i] = i;
}
}
int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
void union_sz(int a, int b){
a = find(a);
b = find(b);
if(sz[a] < sz[b])
swap(a, b);
parent[b] = a;
sz[a] += sz[b];
}
int main()
{
fin >> n >> m;init();
for(int i = 1;i<=m;i++)
fin >> v[i].u >> v[i].v >> v[i].c;
sort(v + 1, v + m + 1);
int cost = 0, alese = 0;
for(int k = 1;k<=m;k++)
{
int i = v[k].u;
int j = v[k].v;
if(find(i) != find(j)){
cost+=v[k].c;
union_sz(i, j);
sol.push_back({i, j});
alese++;
if(alese == n - 1)break;
}
}
fout << cost << endl << n - 1 << endl;
for(auto i : sol)
fout << i.first << " " << i.second << "\n";
return 0;
}