#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct muchie{
long varf1, varf2;
long cost;
}muchii[1000], newArb[1000];
FILE *fout = fopen("apm.out", "w");
long compconex[1000],newNrMuchii;
void randomquick(struct muchie muchii[100], int first, int last){
struct muchie tmp;
int i = first, j = last, pivot;
pivot = muchii[first + rand() % (first + last + 1)].cost;
while (i <= j)
{
while (muchii[i].cost < pivot)
i++;
while (muchii[j].cost > pivot)
j--;
if (i <= j)
{
tmp = muchii[i];
muchii[i++] = muchii[j];
muchii[j--] = tmp;
}
}
if (first < j)
randomquick(muchii, first, j);
if (last>i)
randomquick(muchii, i, last);
}
int find_set(int i)
{
while (compconex[i])
{
i = compconex[i];
}
return i;
}
void kruskal(struct muchie muchii[1000], long compconex[1000], long nrMuchii,long nrNoduri)
{
int i;
for (i = 1; i <= nrNoduri; i++)
{
compconex[i] = 0;
}
int set1, set2,k;
i = 0;
while (i <= nrMuchii && newNrMuchii < nrNoduri - 1)
{
set1 = find_set(muchii[i].varf1);
set2 = find_set(muchii[i].varf2);
if (set1 != set2)
{
newArb[newNrMuchii] = muchii[i];
newNrMuchii++;
compconex[set2] = set1;
}
i++;
}
int cost = 0;
//printf("Kruskal:\n");
for (i = 0; i < newNrMuchii; i++)
{
//printf("%d %d %d\n", newArb[i].varf1, newArb[i].varf2, newArb[i].cost);
cost += newArb[i].cost;
}
fprintf(fout, "%d\n", cost);
fprintf(fout, "%d\n", newNrMuchii);
for (i = 0; i < newNrMuchii; i++)
{
fprintf(fout,"%d %d\n", newArb[i].varf2, newArb[i].varf1);
//cost += newArb[i].cost;
}
//printf("Costul minim este: %d\n", cost);
}
int main()
{
long nrMuchii=0;
FILE *fp = fopen("apm.in", "r");
long i,nrNoduri=0;
int x, y;
fscanf(fp, "%d%d", &x, &y);
while ((fscanf(fp, "%d%d%d", &muchii[nrMuchii].varf1, &muchii[nrMuchii].varf2, &muchii[nrMuchii].cost))!=EOF)
{
nrMuchii++;
if (muchii[nrMuchii-1].varf1 > nrNoduri)
nrNoduri = muchii[nrMuchii-1].varf1;
if (muchii[nrMuchii-1].varf2 > nrNoduri)
nrNoduri = muchii[nrMuchii-1].varf2;
}
nrMuchii--;
srand(time(0)*clock());
randomquick(muchii, 0, nrMuchii);
/*for (i = 0; i <= nrMuchii; i++)
{
fprintf(stdout, "%d %d %d\n", muchii[i].varf1, muchii[i].varf2, muchii[i].cost);
}*/
kruskal(muchii, compconex, nrMuchii, nrNoduri);
fclose(fp);
return 0;
}
/*1 2 7
1 4 5
2 3 8
2 4 9
2 5 7
3 5 5
4 5 15
4 6 6
5 6 8
5 7 9
6 7 11
1 2 4
1 8 8
2 8 11
2 3 8
3 9 2
3 6 4
3 4 7
4 6 14
4 5 9
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7
*/