#include <bits/stdc++.h>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int n, m;
struct DSU
{
int parent[200010];
int size[200010];
void construct(){
for(int i = 1; i <= n; i++){
parent[i] = i;
size[i] = 1;
}
}
int find(int x){
while(parent[x] != x)
x = parent[x];
return x;
}
void unite(int a, int b){
a = find(a);
b = find(b);
if(size[a] > size[b]) swap(a, b);
size[b] += size[a];
parent[a] = b;
}
} dsu;
struct edge
{
int a, b, w;
};
vector<edge> edges;
bool fsort(const struct edge x, const struct edge y)
{
return x.w < y.w;
}
void kruskal()
{
dsu.construct();
vector<pair<int, int>> mste;
int weight = 0;
for(edge &e : edges) if(dsu.find(e.a) != dsu.find(e.b)){
dsu.unite(e.a, e.b);
mste.push_back({e.a, e.b});
weight += e.w;
}
fout << weight << '\n' << mste.size() << '\n';
for(pair<int, int> &e : mste)
fout << e.first << ' ' << e.second << '\n';
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; i++){
int a, b, w; fin >> a >> b >> w;
edges.push_back({a, b, w});
}
sort(edges.begin(), edges.end(), fsort);
kruskal();
return 0;
}