#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct elem{
int st,dr,cost;
}x[400001];
int t[200001],r[200001];
bool comp(elem a,elem b)
{
return a.cost < b.cost;
}
int find(int nod)
{
if(nod == t[nod])
return nod;
else return nod = find(t[nod]);
}
//int t[200001],r[200001];
void unire(int a,int b)
{
int p1 = find(a),p2 = find(b);
if(r[p1] > r[p2])
{
t[p2] = p1;
r[p1]+=r[p2];
}
else{
t[p1] = p2;
r[p2]+=r[p1];
}
}
vector<pair<int,int>>xx;
signed main()
{
freopen ("apm.in","r",stdin);
freopen ("apm.out","w",stdout);
cin >> n >> m;
for(int i = 1;i<=n;++i)
t[i] = i,r[i] = 1;
for(int i = 1;i<=m;++i)
{
cin >> x[i].st >> x[i].dr >> x[i].cost;
}
sort(x+1,x+1+m,comp);
int ans = 0;
for(int i = 1;i<=m;++i)
{
int a = x[i].st,b= x[i].dr;
if(t[a]!=t[b])
{
unire(a,b);
ans+=x[i].cost;
xx.push_back({a,b});
}
}
cout << ans << '\n';
cout << xx.size() << '\n';
for(auto i : xx)
cout << i.first << " " << i.second << '\n';
}