#include <bits/stdc++.h>
using namespace std;
int tati[200005];
vector<pair<int, int>>v;
struct lat
{
int x, y, cost;
};
lat d[400005];
bool cmp(lat &a, lat &b)
{
return(a.cost < b.cost);
}
int gasire(int x)
{
if(tati[x] == x)return x;
tati[x] = gasire(tati[x]);
return tati[x];
}
void unire(int a, int b)
{
a = gasire(a);
b = gasire(b);
if(a!=b)
{
tati[b] = a;
}
}
int main()
{
ifstream cin("apm.in");
ofstream cout("apm.out");
int n, m, k, j, c;
cin >> n >> m;
for(int i = 1; i<= n; i++)
{
tati[i] = i;
}
for(int i = 1; i<= m; i++)
{
cin >> k >> j >> c;
d[i].x = k;
d[i].y = j;
d[i].cost = c;
}
sort(d+1, d+m+1, cmp);
int cos = 0;
int muc = 0;
for(int i = 1; i<= m; i++)
{
int nr1 = d[i].x;
int nr2 = d[i].y;
if(gasire(nr1) != gasire(nr2))
{
cos+=d[i].cost;
muc++;
v.push_back({nr1, nr2});
unire(nr1, nr2);
}
if(muc == n-1)break;
}
cout << cos << '\n';
cout << v.size()<<'\n';
for( auto i: v)
{
cout << i.first <<" "<< i.second <<'\n';
}
return 0;
}