Cod sursa(job #903141)
#include <stdio.h>
#include <list>
#include <algorithm>
#include <utility>
using namespace std;
#define Nmax 200005
#define Mmax 400005
struct edge{
int x, y, cost;
};
int n, m, sol;
int ind[Mmax], rang[Mmax], rad[Mmax];
edge edges[Mmax];
list < pair<int, int> > a;
list < pair<int, int> >::iterator it;
struct compare{
bool operator() (int i, int j){return edges[i].cost < edges[j].cost;}
};
compare comp;
void read(){
scanf("%i %i", &n, &m);
for(register int i = 1; i <= m; ++i){
scanf("%i %i %i", &edges[i].x, &edges[i].y, &edges[i].cost);
ind[i] = i;
rang[i] = 1;
rad[i] = i;
}
fclose(stdin);
}
int find(int x){
int r = x, aux;
while(r != rad[r]) r = rad[r];
while(x != r){
aux = rad[x];
rad[x] = r;
x = aux;
}
return r;
}
void unite(int x, int y){
if(rang[x] > rad[y])
rad[y] = x;
else
rad[x] = y;
if(rang[x] == rang[y]) ++rang[y];
}
void minim(){
int rad1, rad2;
sort(ind+1, ind+m+1, comp);
for(int i = 1; i <= m; ++i){
rad1 = find(edges[ ind[i] ].x);
rad2 = find(edges[ ind[i] ].y);
if(rad1 != rad2){
unite(rad1, rad2);
sol += edges[ ind[i] ].cost;
a.push_back( make_pair(edges[ ind[i] ].x, edges[ ind[i] ].y) );
}
}
}
void write(){
printf("%i\n%i\n", sol, n-1);
for(it = a.begin(); it != a.end(); ++it)
printf("%i %i\n", it->first, it->second);
}
int main(){
freopen("apm.in", "r", stdin);
freopen("apm.out", "w", stdout);
read();
minim();
write();
fclose(stdout);
return 0;
}