#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>

#define MAXN 1001
#define MAXK 11
#define INFTY 1e10
#define MAX_EXECUTION_TIME 120
#define MAX_ITERATIONS 2000
#define EPS 1e-6

//char inFile [] = "mmsfp.01.txt";
//char outFile [] = "mmsfp.01.out";
char inFile [] = "podela.10.in";
char outFile [] = "podela.10.out";

int n, m, k;
// matrix weight
double w [MAXN][MAXN];

// adjacency list
int adj [MAXN][MAXN];
// sorted list of vertices
int sorted [MAXN][MAXN];
// all edges 
int edge1 [MAXN * MAXN];
int edge2 [MAXN * MAXN];
int sorted_edges [MAXN * MAXN];
// root vertices
int root [MAXN];

double d [MAXN];
int p [MAXN];
int mark [MAXN];

// weight of trees
double weight [MAXN];
// max (weight [i])
double max_weight;
// sum (weight [i])
double sum_weight;
// index of vertices
int index [MAXN];
// trees with indices
int trees [MAXK][MAXN];
// parent vertices in trees
int parent [MAXN];
// adjacent vertices in trees
int adj_trees [MAXN][MAXN];

// weight of trees
double weight_optimal [MAXN];
// max (weight [i])
double max_weight_optimal;
// sum (weight [i])
double sum_weight_optimal;
// index of vertices
int index_optimal [MAXN];
// trees with indices
int trees_optimal [MAXK][MAXN];
// parent vertices in trees
int parent_optimal [MAXN];
// adjacent vertices in trees
int adj_trees_optimal [MAXN][MAXN];

// maximum number of neighborhoods
int max_neighborhoods;
// number of iterations
int iterations;

// time elapsed from starting program
double elapsed_time;
// best solution time
double best_time;
// start time
clock_t start;
// finish time
clock_t finish;

// Measuring switch, move, prim
double time_switch, time_move, time_prim, time_shaking;
int count_switch, count_move, count_prim;
int count_switch_improve, count_move_improve, count_prim_improve;

double max_greedy;

void input()
{
	FILE *in = fopen (inFile, "r");
	fscanf (in, "%d %d", &n, &m);
	fscanf (in, "%d", &k);
	for (int i = 0; i < k; i++)
	{
		fscanf (in, "%d", &root [i]);
		root [i]--;
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			w [i][j] = -1.0;
			adj [i][j] = 0;
		}
	int x, y;
	double z;
	for (int i = 0; i < m; i++)
	{
		fscanf (in, "%d %d %lf", &x, &y, &z);
		x--;
		y--;
		w [x][y] = z;
		w [y][x] = z;
		adj [x][0]++;
		adj [x][adj [x][0]] = y;
		adj [y][0]++;
		adj [y][adj [y][0]] = x;
		edge1 [i] = x;
		edge2 [i] = y;
	}
	fclose (in);
}

bool check ()
{
	for (int i = 0; i < n; i++)
		if ((index_optimal [i] < 0) || (index_optimal [i] >= k))
			return false;
	for (int i = 0; i < n; i++)
		mark [i] = 0;
	for (int i = 0; i < k; i++)
	{
		mark [root [i]] = 1;
		if (parent_optimal [root [i]] > -1)
			return false;
	}
	for (int i = 0; i < n; i++)
	{
		if ((parent_optimal [i] == -1) && (mark [i] == 0))
			return false;
		if ((parent_optimal [i] > -1) && (w [i][parent_optimal [i]] < 0))
			return false;
	}
	for (int i = 0; i < k; i++)
		weight_optimal [i] = 0.0;
	for (int i = 0; i < n; i++)
		if (parent_optimal [i] != -1)
			weight_optimal [index_optimal [i]] += w [i][parent_optimal [i]];
	double max = weight_optimal [0];
	for (int i = 1; i < k; i++)
		if (max < weight_optimal [i])
			max = weight_optimal [i];

	if (fabs (max - max_weight_optimal) > EPS)
		return false;
	return true;	
}

void output()
{
	FILE *out = fopen (outFile, "w");
	fprintf (out, "N = %d\t M = %d\n", n, m);
	fprintf (out, "%0.3lf (%0.3lf)\n", max_weight_optimal, max_greedy);
	for (int i = 0; i < k; i++)
		fprintf (out, "%0.3lf ", weight_optimal [i]);
	fprintf (out, "\n");
	for (int i = 0; i < n; i++)
		fprintf (out, "%d ", index_optimal [i] + 1);
	fprintf (out, "\n");
	if (check () == true)
		fprintf (out, "OK!\n");
	else
		fprintf (out, "NOT OK!\n");
	fprintf (out, "\n");

	fprintf (out, "HEURISTICS = %0.3lf\n", max_weight);
	for (int i = 0; i < k; i++)
		fprintf (out, "%0.3lf ", weight [i]);
	fprintf (out, "\n");
	for (int i = 0; i < n; i++)
		fprintf (out, "%d ", index [i] + 1);
	fprintf (out, "\n");
	fprintf (out, "ERROR = %0.3lf\n", 100 * ((max_weight_optimal * k - sum_weight) / sum_weight));
	fprintf (out, "\n");
	fprintf (out, "TIMES = %0.3lf (%0.3lf)\n", elapsed_time, best_time);
	fprintf (out, "ITERATIONS = %d\n", iterations);
	fprintf (out, "SWITCH = %d (%d)\t TIME = %0.3lf\n", count_switch, count_switch_improve, time_switch);
	fprintf (out, "MOVE = %d (%d)\t TIME = %0.3lf\n", count_move, count_move_improve, time_move);
	fprintf (out, "PRIM = %d (%d)\t TIME = %0.3lf\n", count_prim, count_prim_improve, time_prim);
	fprintf (out, "SHAKING = %0.3lf\n", time_shaking);
	fclose (out);
}

void input_comp()
{
	FILE *in = fopen (inFile, "r");
	fscanf (in, "%d %d", &n, &m);
	k = 2;
	fscanf (in, "%d %d", &root [0], &root [1]);
	root [0]--;
	root [1]--;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			w [i][j] = -1.0;
			adj [i][j] = 0;
		}
	int x, y;
	double z;
	for (int i = 0; i < m; i++)
	{
		fscanf (in, "%d %d %lf", &x, &y, &z);
		x--;
		y--;
		w [x][y] = z;
		w [y][x] = z;
		adj [x][0]++;
		adj [x][adj [x][0]] = y;
		adj [y][0]++;
		adj [y][adj [y][0]] = x;
		edge1 [i] = x;
		edge2 [i] = y;
	}
	fclose (in);
}

void output_comp()
{
	FILE *out = fopen (outFile, "w");
	for (int i = 0; i < k; i++)
		fprintf (out, "%0.3lf ", weight_optimal [i]);
	fprintf (out, "\n");
	for (int i = 0; i < k; i++)
	{
		fprintf (out, "%d %d\n", trees_optimal [i][0], trees_optimal [i][0] - 1);
		double ww = 0.0;
		for (int j = 0; j < n; j++)
			if ((index_optimal [j] == i) && (parent_optimal [j] != -1))
			{
				fprintf (out, "%d %d\n", j + 1, parent_optimal [j] + 1);
				ww += w [j][parent_optimal [j]];
			}
		printf ("%lf %lf\n", weight_optimal [i], ww);
	}
	fclose (out);
}

void calculate_weights ()
{
	for (int i = 0; i < k; i++)
		weight [i] = 0.0;
	for (int i = 0; i < n; i++)
		if (parent [i] != -1)
			weight [index [i]] += w [i][parent [i]];
}

double calculate_max ()
{
	double max = weight [0];
	for (int i = 1; i < k; i++)
		if (max < weight [i])
			max = weight [i];
	return max;
}

double calculate_sum ()
{
	double sum = 0.0;
	for (int i = 0; i < k; i++)
		sum += weight [i];
	return sum;
}

int compare (const void *a, const void *b)
{
	double x = d [*(int*) a];
	double y = d [*(int*) b];
	if (x < y)
		return -1;
	else if (y < x)
		return 1;
	else
		return 0;
}

int compare1 (const void *a, const void *b)
{
	int i = *(int*) a;
	int j = *(int*) b;
	double x = w [edge1 [i]][edge2 [i]];
	double y = w [edge1 [j]][edge2 [j]];
	if (x < y)
		return -1;
	else if (y < x)
		return 1;
	else
		return 0;
}

void set_optimal()
{
	max_weight_optimal = max_weight;
	sum_weight_optimal = sum_weight;
	for (int i = 0; i < k; i++)
		weight_optimal [i] = weight [i];
	for (int i = 0; i < n; i++)
	{
		index_optimal [i] = index [i];
		parent_optimal [i] = parent [i];
	}
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			adj_trees_optimal [i][j] = adj_trees [i][j];
	for (int i = 0; i < k; i++)
		for (int j = 0; j <= n; j++)
			trees_optimal [i][j] = trees [i][j];
}

void set_current()
{
	max_weight = max_weight_optimal;
	sum_weight = sum_weight_optimal;
	for (int i = 0; i < k; i++)
		weight [i] = weight_optimal [i];
	for (int i = 0; i < n; i++)
	{
		index [i] = index_optimal [i];
		parent [i] = parent_optimal [i];
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= n; j++)
			adj_trees [i][j] = adj_trees_optimal [i][j];
	for (int i = 0; i < k; i++)
		for (int j = 0; j <= n; j++)
			trees [i][j] = trees_optimal [i][j];
}

void add_edge (int v, int u)
{
	adj_trees [v][0]++;
	adj_trees [v][adj_trees [v][0]] = u;
	adj_trees [u][0]++;
	adj_trees [u][adj_trees [u][0]] = v;
}

void greedy ()
{
	for (int i = 0; i < n; i++)
	{
		index [i] = -1;
		parent [i] = -1;
	}
	for (int i = 0; i < k; i++)
		for (int j = 0; j <= n; j++)
			trees [i][j] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= n; j++)
			adj_trees [i][j] = 0;
	for (int i = 0; i < k; i++)
	{
		index [root [i]] = i;
		weight [i] = 0.0;
		trees [i][0] = 1;
		trees [i][1] = root [i];
	}
	for (int i = k; i < n; i++)
	{
		double global_max = INFTY;
		double global_sum = INFTY;
		int vmin = -1;
		int umin = -1;
		for (int j = 0; j < m; j++)
		{
			int v = edge1 [sorted_edges [j]];
			int u = edge2 [sorted_edges [j]];
			if (((index [v] == -1) && (index [u] != -1)) || ((index [v] != -1) && (index [u] == -1)))
			{
				if (index [v] != -1)
					weight [index [v]] += w [u][v];
				if (index [u] != -1)
					weight [index [u]] += w [u][v];
				double new_max = calculate_max();
				double new_sum = calculate_sum();
				if ((new_max + EPS < global_max) || ((fabs (new_max - global_max) < EPS) && (new_sum < global_sum)))
				{
					global_max = new_max;
					global_sum = new_sum;
					vmin = v;
					umin = u;
				}
				if (index [v] != -1)
					weight [index [v]] -= w [u][v];
				if (index [u] != -1)
					weight [index [u]] -= w [u][v];
			}
		}
		if (index [vmin] != -1)
		{
			weight [index [vmin]] += w [umin][vmin];
			index [umin] = index [vmin];
			parent [umin] = vmin;
			trees [index [vmin]][0]++;
			trees [index [vmin]][trees [index [vmin]][0]] = umin;
		}
		else if (index [umin] != -1)
		{
			weight [index [umin]] += w [umin][vmin];
			index [vmin] = index [umin];
			parent [vmin] = umin;
			trees [index [umin]][0]++;
			trees [index [umin]][trees [index [umin]][0]] = vmin;
		}
		else
			printf ("ERROR!\n");
		add_edge (vmin, umin);
	}
	calculate_weights();
	max_weight = calculate_max();
	sum_weight = calculate_sum();
	max_greedy = max_weight;
}

void init ()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= adj [i][0]; j++)
		{
			p [j - 1] = adj [i][j];
			d [j - 1] = w [i][adj [i][j]];
		}
		qsort (p, adj [i][0], sizeof (int), compare);
		for (int j = 1; j <= adj [i][0]; j++)
			sorted [i][j] = p [j - 1];
	}
	for (int i = 0; i < m; i++)
		sorted_edges [i] = i;
	qsort (sorted_edges, m, sizeof (int), compare1);

	greedy ();
	set_optimal();
	max_neighborhoods = 2 * (int)(sqrt ((double) n)) + 1;

	count_switch = 0;
	count_switch_improve = 0;
	time_switch = 0.0;
	count_move = 0;
	count_move_improve = 0;
	time_move = 0.0;
	count_prim = 0;
	count_prim_improve = 0;
	time_prim = 0.0;
	time_shaking = 0.0;
}

bool prim (int k)
{
	for (int i = 0; i < n; i++)
	{
		d [i] = INFTY;
		p [i] = -1;
		mark [i] = 0;
	}
	d [root [k]] = 0;
	double sum = 0.0;

	for (int i = 1; i <= trees [k][0]; i++)
	{
		int ind = -1;
		for (int j = 1; j <= trees [k][0]; j++)
		{
			if ((mark [trees [k][j]] == 0) && ((ind == -1) || (d [trees [k][j]] < d [ind])))
				ind = trees [k][j];
		}
		if (ind == -1)
			return false;
		mark [ind] = 1;
		if (p [ind] != -1)
			sum += w [ind][p [ind]];
		for (int j = 1; j <= adj [ind][0]; j++)
		{
			int v = adj [ind][j];
			if ((index [v] == k) && (mark [v] == 0))
			{
				if (w [ind][v] < 0)
					printf ("ERROR!\n");
				if (w [ind][v] < d [v])
				{
					d [v] = w [ind][v];
					p [v] = ind;
				}
			}
		}
	}
	if (sum + EPS < weight [k])
		return true;
	else
		return false;
}

void fix_adj_trees (int k)
{
	for (int i = 1; i <= trees [k][0]; i++)
		adj_trees [trees [k][i]][0] = 0;
	for (int i = 1; i <= trees [k][0]; i++)
		if (parent [trees [k][i]] != -1)
			add_edge (trees [k][i], parent [trees [k][i]]);
}

bool prim ()
{
	bool improved = false;
	for (int i = 0; i < k; i++)
	{
		if (prim (i) == true)
		{
			for (int j = 1; j <= trees [i][0]; j++)
				parent [trees [i][j]] = p [trees [i][j]];
			fix_adj_trees (i);
			improved = true;
//			calculate_weights();
//			max_weight = calculate_max();
//			sum_weight = calculate_sum();
//			printf ("%0.3lf %0.3lf\n", max_weight, sum_weight);
		}
	}
	calculate_weights();
	max_weight = calculate_max();
	sum_weight = calculate_sum();
	return improved;
}

void dfs (int i, int t)
{
	mark [i] = 1;
	if (t != -1)
	{
		index [i] = t;
		trees [t][0]++;
		trees [t][trees [t][0]] = i;
	}
	d [i] = 0.0;
	for (int j = 1; j <= adj [i][0]; j++)
	{
		if ((parent [adj [i][j]] == i) && (mark [adj [i][j]] == 0))
		{
			dfs (adj [i][j], t);
			d [i] = d [i] + d [adj [i][j]] + w [i][adj [i][j]];
		}
	}
}

bool edge_switch ()
{
	bool improved = false;
	for (int i = 0; i < n; i++)
		mark [i] = 0;
	for (int i = 0; i < k; i++)
		dfs (root [i], -1);

	for (int i = 0; i < n; i++)
		if (parent [i] != -1)
		{
			for (int j = 0; j < n; j++)
				mark [j] = 0;
			for (int j = 0; j < n; j++)
				if ((index [i] != index [j]) && (parent [j] != -1))
				{
					if ((w [j][parent [i]] > 0) && (w [i][parent [j]] > 0))
					{
						weight [index [i]] = weight [index [i]] - w [i][parent [i]] - d [i] + w [parent [i]][j] + d [j];
						weight [index [j]] = weight [index [j]] - w [j][parent [j]] - d [j] + w [parent [j]][i] + d [i];
						double new_max = calculate_max();
						double new_sum = calculate_sum();
						if ((new_max + EPS < max_weight) || ((fabs (new_max - max_weight) < EPS) && (new_sum < sum_weight)))
						{
							int ptmp = parent [i];
							parent [i] = parent [j];
							parent [j] = ptmp;
							max_weight = new_max;
							sum_weight = new_sum;

							int ri = index [parent [i]];
							trees [ri][0] = 0;
							dfs (root [ri], ri);
							int rj = index [parent [j]];
							trees [rj][0] = 0;
							dfs (root [rj], rj);
							improved = true;
							break;
						}
						else
						{
							weight [index [i]] = weight [index [i]] + w [i][parent [i]] + d [i] - w [parent [i]][j] - d [j];
							weight [index [j]] = weight [index [j]] + w [j][parent [j]] + d [j] - w [parent [j]][i] - d [i];
						}
					}
				}
		}
	if (improved == true)
	{
		for (int i = 0; i < k; i++)
			fix_adj_trees (i);
	}
	return improved;
}

bool vertex_move ()
{
	bool improved = false;
	for (int i = 0; i < n; i++)
		if ((adj_trees [i][0] == 1) && (parent [i] != -1))
		{
			for (int j = 0; j < n; j++)
				mark [j] = 0;
			for (int j = 1; j <= adj [i][0]; j++)
				if (index [adj [i][j]] != index [i])
				{
					int v = adj [i][j];
					weight [index [i]] = weight [index [i]] - w [i][parent [i]];
					weight [index [v]] = weight [index [v]] + w [i][v];
					double new_max = calculate_max();
					double new_sum = calculate_sum();
					if ((new_max + EPS < max_weight) || ((fabs (new_max - max_weight) < EPS) && (new_sum < sum_weight)))
					{
						max_weight = new_max;
						sum_weight = new_sum;

						int ind = index [i];
						parent [i] = v;
						index [i] = index [v];
						trees [index [v]][0]++;
						trees [index [v]][trees [index [v]][0]] = i;
						trees [ind][0] = 0;
						dfs (root [ind], ind);
//						printf ("%d %d\n", i, v);
//						for (int k = 1; k <= trees [ind][0]; k++)
//							printf ("%d (%d), ", trees [ind][k], parent [trees [ind][k]]);
//						printf ("\n");
						adj_trees [i][0] = 0;
						add_edge (i, v);
						improved = true;
						break;
					}
					else
					{
						weight [index [i]] = weight [index [i]] + w [i][parent [i]];
						weight [index [v]] = weight [index [v]] - w [i][v];
					}
				}
			if (improved == true)
				break;
		}
	if (improved == true)
	{
		for (int i = 0; i < k; i++)
			fix_adj_trees (i);
	}
	return improved;
}

void shaking (int nk)
{
	clock_t s = clock();
	int x = rand() % nk;
	int y = nk - x;
	while (x > 0)
	{
		x--;
		int i = rand () % n;
		int j = rand () % n;
		int count = 0;
		while ((parent [i] == -1) || (parent [j] == -1) || (index [i] == index [j]) || (w [i][parent [j]] < 0) || (w [j][parent [i]] < 0))
		{
			count++;
			if (count == 100)
				break;
//			printf ("*** %d %d\t %d %d\t %d %d\n", i, j, parent [i], parent [j], index [i], index [j]);
			i = rand () % n;
			j = rand () % n;
		}
		if (count == 100)
			break;
		int tmp = parent [i];
		parent [i] = parent [j];
		parent [j] = tmp;
		trees [index [parent [i]]][0] = 0;
		trees [index [parent [j]]][0] = 0;
		for (int k = 0; k < n; k++)
			mark [k] = 0;
		dfs (root [index [parent [i]]], index [parent [i]]);
		dfs (root [index [parent [j]]], index [parent [j]]);
	}
	calculate_weights();
	max_weight = calculate_max();
	sum_weight = calculate_sum();
	for (int i = 0; i < k; i++)
		fix_adj_trees (i);

	while (y > 0)
	{
		y--;
		int i = rand () % n;
		int j = rand () % n;
		int count = 0;
		while ((parent [i] == -1) || (adj_trees [i][0] != 1) || (index [i] == index [j]) || (w [i][j] < 0))
		{
			count++;
			if (count == 100)
				break;
//			printf ("+++ %d %d\t %d %d\t %d %d\t %d\n", i, j, parent [i], parent [j], index [i], index [j], adj_trees [i][0]);
			i = rand () % n;
			j = rand () % n;
		}
		if (count == 100)
			break;

		int ind = index [i];
		parent [i] = j;
		index [i] = index [j];
		trees [index [j]][0]++;
		trees [index [j]][trees [index [j]][0]] = i;
		trees [ind][0] = 0;
		for (int k = 0; k < n; k++)
			mark [k] = 0;
		dfs (root [ind], ind);
		adj_trees [i][0] = 0;
		add_edge (i, j);
	}
	calculate_weights();
	max_weight = calculate_max();
	sum_weight = calculate_sum();

	time_shaking += (double(clock ()) - double(s)) / CLOCKS_PER_SEC;
}

void local_search ()
{
//	printf ("START: %0.3lf\n", max_weight);
	int index = 0;
	while (index < 3)
	{
//		printf ("LS %d %0.3lf %0.3lf\n", index, max_weight, sum_weight);
//		double tmp = max_weight;
//		calculate_weights();
//		max_weight = calculate_max();
//		if (tmp != max_weight)
//			printf ("ERROR!\n");
		if (index == 0)
		{
			clock_t s = clock();
			while (edge_switch() == true)
			{
				count_switch++;
				count_switch_improve++;
			}
			count_switch++;
			time_switch += (double(clock ()) - double(s)) / CLOCKS_PER_SEC;
			index++;
		}
		else if (index == 1)
		{
			clock_t s = clock();
			bool improved = false;
			while (vertex_move() == true)
			{
				improved = true;
				count_move++;
				count_move_improve++;
			}
			count_move++;
			time_move += (double(clock ()) - double(s)) / CLOCKS_PER_SEC;
			if (improved == true)
				index = 0;
			else
				index++;
		}
		else if (index == 2)
		{
			clock_t s = clock();
			if (prim() == true)
			{
				count_prim_improve++;
				index = 0;
			}
			else
				index++;
			count_prim++;
			time_prim += (double(clock ()) - double(s)) / CLOCKS_PER_SEC;
		}
	}
//	printf ("FINISH: %0.3lf\n", max_weight);
}

void vns ()
{
	start = clock();
	int nk = 1;
	iterations = 0;
	while (iterations <= MAX_ITERATIONS)
	{
		printf ("%d %d: %0.3lf %0.3lf\n", iterations, nk, max_weight, max_weight_optimal);
		finish = clock();
		elapsed_time = (double(finish) - double(start)) / CLOCKS_PER_SEC;
		if (elapsed_time > MAX_EXECUTION_TIME)
			break;

		set_current();
		shaking (nk);
		local_search ();
		if ((max_weight + EPS < max_weight_optimal) || ((fabs (max_weight - max_weight_optimal) < EPS) && (sum_weight < sum_weight_optimal)))
		{
			finish = clock();
			best_time = (double(finish) - double(start)) / CLOCKS_PER_SEC;
			nk = 1;
			set_optimal();
		}
		else
		{
			nk++;
			if (nk == max_neighborhoods)
				nk = 1;
		}
		iterations++;
	}

	finish = clock();
	elapsed_time = (double(finish) - double(start)) / CLOCKS_PER_SEC;
}

int find (int i)
{
	if (i != p [i])
		p [i] = find (p [i]);
	return p [i];
}

void make_union (int i, int j)
{
	int x = find (i);
	int y = find (j);
	if (x != y)
	{
		if (mark [x] > mark [y])
			p [y] = x;
		else if (mark [x] < mark [y])
			p [x] = y;
		else
		{
			p [y] = x;
			mark [y]++;
		}
		add_edge (i, j);
		sum_weight += w [i][j];
	}
}

void dfs1 (int i, int color)
{
	index [i] = color;
	trees [color][0]++;
	trees [color][trees [color][0]] = i;
	for (int j = 1; j <= adj_trees [i][0]; j++)
		if (index [adj_trees [i][j]] == -1)
		{
			parent [adj_trees [i][j]] = i;
			dfs1 (adj_trees [i][j], color);
		}
}

void heuristics()
{
	for (int i = 0; i < n; i++)
	{
		index [i] = -1;
		parent [i] = -1;
	}
	for (int i = 0; i < k; i++)
		for (int j = 0; j <= n; j++)
			trees [i][j] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= n; j++)
			adj_trees [i][j] = 0;
	sum_weight = 0.0;

	for (int i = 0; i < n; i++)
	{
		p [i] = i;
		mark [i] = 1;
	}
	for (int i = 0; i < k; i++)
		p [root [i]] = root [0];
	for (int i = 0; i < m; i++)
	{
		int x = edge1 [sorted_edges [i]];
		int y = edge2 [sorted_edges [i]];
//		printf ("%lf\n", w [x][y]);
		make_union (x, y);
	}
	
	for (int i = 0; i < k; i++)
		dfs1 (root [i], i);
	calculate_weights();
	max_weight = calculate_max();
	if (fabs (sum_weight - calculate_sum()) > EPS)
		printf ("ERROR! %0.3lf %0.3lf\n", sum_weight, calculate_sum());
}


int main ()
{
	input_comp ();
	init ();
	vns ();
	heuristics ();
	output_comp ();
	printf ("%d\n", check());
	return 0;
}