
#include 
#include 
#include 
#include 

#ifdef WIN32

int getchar_unlocked() { return getchar(); }

#elif UNIX
/* Do linux stuff */
#endif

using namespace std;

struct edge;

typedef struct node {
    int id;
    vector connections;
    bool server = false;
    bool server_origin = false;
    bool deleted = false;
    bool start = false;
    int virtual_size = 0;
} node_t;

typedef struct edge {
    node_t *from;
    node_t *to;
    int cost;

    bool deleted() {
        return to->deleted || from->deleted;
    }
} edge_t;

static inline void scanint(int &x) {
    // fastest stdin reading, found on https://stackoverflow.com/questions/27899413/understanding-getchar-unlocked
    register int c = getchar_unlocked();
    x = 0;
    for (; (c < 48 || c > 57); c = getchar_unlocked());
    for (; c > 47 && c < 58; c = getchar_unlocked()) {
        x = (x << 1) + (x << 3) + (c & 15);
    }
}

int main() {
    int edges_count, servers_count;
    scanf("%d %d", &edges_count, &servers_count);

    vector nodes(static_cast(edges_count));
    vector circle_nodes;

    unsigned int total_cost = 0;
    unsigned int confirmed_cost = 0; // cena jen pro originÃ¡lnÃ servery

    bool created[edges_count] = {false};

    for (int i = 0; i < edges_count; ++i) {
        int from, to, cost;
        scanint(from);
        scanint(to);
        scanint(cost);

        if (!created[from]) {
            nodes[from] = new node_t();
            created[from] = true;
        }

        if (!created[to]) {
            nodes[to] = new node_t();
            created[to] = true;
        }

        edge_t e1, e2;
        e1.to = nodes[to];
        e1.from = nodes[from];

        e2.to = nodes[from];
        e2.from = nodes[to];

        e2.cost = e1.cost = cost;
        nodes[from]->connections.push_back(e1);
        nodes[from]->virtual_size++;

        nodes[from]->id = from;
        nodes[to]->connections.push_back(e2);
        nodes[to]->virtual_size++;

        nodes[to]->id = to;
    }

    int server_ids[servers_count] = {0};
    node_t *start;

    // pÅ™idÃ¡nÃ serverÅ¯ a startu
    for (int i = 0; i < servers_count; ++i) {
        int id;
        scanint(id);
        nodes[id]->server = true;
        nodes[id]->server_origin = true;
        server_ids[i] = id;

        if (i == 0) {
            nodes[id]->start = true;
            start = nodes[id];
        }
    }

    stack leaves;

    // pÅ™idÃ¡nÃ listÅ¯ do stacku
    for (int i = 0; i < nodes.size(); ++i) {
        if (!nodes[i]->deleted && nodes[i]->connections.size() == 1) {
            leaves.push(nodes[i]);
        }

        while (!leaves.empty()) {
            node_t *current = leaves.top();
            leaves.pop();

            if (current->server_origin) {
                confirmed_cost = total_cost;
            }

            node_t *next;
            int x;

            // smaÅ¾ zakÃ¡zanÃ© hrany
            for (x = 0; x < current->connections.size(); ++x) {
                if (!current->connections[x].deleted()) {
                    next = current->connections[x].to;
                    break;
                }
            }

            // pokud jdu ze serveru
            if (current->server) {
                next->server = true;
                total_cost += 2 * current->connections[x].cost; // tam a zpÄ›t
            }

            if (current->start) {
                next->start = true;
            }

            current->deleted = true;
            next->virtual_size--;
            if (next->virtual_size == 1)
                leaves.push(next);
        }
    }



    // Zjistit jestli nenÃ kruÅ¾nice reundandnÃ
    int found = 0;
    for (int i = 0; i < nodes.size(); ++i) {
        if (nodes[i]->deleted) continue;
        if (nodes[i]->server) {
            start = nodes[i];
            found++;
        }
    }

    if (found == 1) {
        // kruÅ¾nice je nepotÅ™ebnÃ¡
        printf("%d\n", confirmed_cost);
        exit(0);
    }


    int biggestCostBetweenservers = 0;
    int circleCost = 0;
    int temporaryEdgeCost = 0;

    int iterationCounter = 0;
    node_t *current = start;

    while (true) {
        ++iterationCounter;
        if (current == start && iterationCounter > 1) {
            if (temporaryEdgeCost > biggestCostBetweenservers) {
                biggestCostBetweenservers = temporaryEdgeCost;
            }
            goto konec;
        }

        if (current->server && temporaryEdgeCost > biggestCostBetweenservers) {
            biggestCostBetweenservers = temporaryEdgeCost;
            temporaryEdgeCost = 0;
        } else if (current->server)
            temporaryEdgeCost = 0;


        for (int i = 0; i < current->connections.size(); ++i) {
            if (iterationCounter > 2 && current->connections[i].to == start) {
                circleCost += current->connections[i].cost;
                temporaryEdgeCost += current->connections[i].cost;
                current->deleted = true;
                current = current->connections[i].to;
                goto dalsiIerace;
            }

            if (!current->connections[i].deleted()) {
                circleCost = circleCost + current->connections[i].cost;
                temporaryEdgeCost = temporaryEdgeCost + current->connections[i].cost;
                current->deleted = true;
                current = current->connections[i].to;
                goto dalsiIerace;
            }
        }

        dalsiIerace:;
    }

    konec:
    int n = 2 * (circleCost - biggestCostBetweenservers);
    printf("%d\n", (n < circleCost ? 2 * (circleCost - biggestCostBetweenservers) : circleCost) + total_cost);
    return 0;
}

===== 2. nejrychlejší v C/C++ =====


#include 
#include 
#include 
#include 
#include 

//ZKOUSIM ZAPOCITAT MEZERU
int all_servers;
unsigned char *used;
unsigned char *done_socket;
unsigned char *visited;
unsigned char *help_visited;
unsigned char *side;
unsigned char *zapocitat;
int *queue;
int *neighbour_counter;
int *opposite_neigh;
unsigned char * keys;

int bfs_count = 0;
int done = 0;
int rear = 0;

struct node {
    int value;
    int price;
    int edge_number;
    struct node* next;
};

struct Graph {
    struct node** adjLists;
    int numElements;
};

struct node* createNode(int vertex, int price, int edge_number) {
    struct node* newNode = malloc(sizeof(struct node));
    newNode->next = NULL;
    newNode->value = vertex; //do struktury node mam podle me pridat hranu a tady to pak musim inicializovat
    newNode->price = price;
    newNode->edge_number = edge_number;
    return newNode;
}
 
  void printmatrixchar(int rows, unsigned char* arr){
    for(int i =0; inext = graph->adjLists[src];
    graph->adjLists[src] = newNode;
 
    //pridavam hranu z druheho prvku do prvniho
    newNode = createNode(src, val, edge);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

/*void deleteEdge(struct Graph* graph, int src, int dest, int val, int edge) {
    //pridavam hranu z prvniho prvku do druheho
    struct node* newNode = graph->adjLists[src];//createNode(dest, val, edge);
    
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
 
    //pridavam hranu z druheho prvku do prvniho
    newNode = createNode(src, val, edge);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}*/


//vytvorim adjacency List o "elements" prvcich
struct Graph* createGraph(int elements) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numElements = elements; 
    graph->adjLists = malloc(elements * sizeof(struct node*)); 
    for (int i = 0; i < elements; i++)
        graph->adjLists[i] = NULL; // prozatim na NULL
    return graph;
}

//prohleda mi adjacency List do sirky a vrati sokety
int bfs(int v, struct Graph* graph) {
	memcpy(help_visited,visited,sizeof(char)*all_servers); // VZDY PREPISU NOVE
	int front = 0; rear = 0;
 	if (bfs_count == 0) {
 		for (int i=0; iadjLists[u];   
             
        while (temp)	{//dokud prvek s necim sousedi
         //  if(!used[temp->value]) { //pokud uz jsem z nej neprohledavala
           		if (help_visited[temp->value]) {
           			if(keys[temp->value] == 1) {
           				return temp->value;
           			}
           			queue[rear] = temp->value;
           			rear++;
           			help_visited[temp->value] = 0; 
           			
           	
           		}
           		/*else { //tohle mi vubec nenastane
            		done = 1;
            		if (keys[temp->value] == '1') {
            			done = 1;
            		}
            		return;
  				}	*/
			
            temp = temp->next;
		}
    }
	return -1;
}
/*void freeGraph(struct Graph* graph, int m) {
    int i;
    for (i = 0; i < m; ++i) {
        free(graph->adjLists[i]);
    }
    //free(a);
    free(graph);
} */


int main(int argc, char *argv[])
{
	clock_t start = clock(); 

//	int connections;
	//int first_connected;
	//int second_connected;





int key_servers; // cislovani serveru je od 0
int label1;
int label2;
int transfer_time;
int key_serv;
int final_price = 0;

	
	if (scanf("%d %d", &all_servers, &key_servers) != 2) {
		 printf("Input is wrong!");
		 return 2;
	}
	struct Graph* graph = createGraph(all_servers);
	visited = calloc(all_servers, sizeof(unsigned char));
	
	help_visited = calloc(all_servers, sizeof(unsigned char));
	
	neighbour_counter = calloc(all_servers, sizeof(int));
	opposite_neigh = calloc(all_servers, sizeof(int));
	used = calloc(all_servers, sizeof(unsigned char));
	queue = calloc(all_servers, sizeof(int));
	keys = calloc(all_servers, sizeof(unsigned char));
	//side = calloc(all_servers, sizeof(unsigned char));
	zapocitat = calloc(all_servers, sizeof(unsigned char));


	//plnim adj. graf
	for (int i=0; i< all_servers; i++) {
		scanf("%d %d %d", &label1, &label2, &transfer_time);
		addEdge(graph, label1, label2, transfer_time, i);
		neighbour_counter[label1]++;
		neighbour_counter[label2]++;
	}	
	
	for (int i=0; iadjLists[list_start];
					while (visited[temp->value]) {
						temp = temp->next;
					}
					if (zacinam_pocitat == 0) { 
						if ((keys[list_start] == 1) || (zapocitat[list_start] == 1)) { //OVERIM, JESTLI NEJEDU Z NODU S MEZEROU
							zacinam_pocitat = 1;
						}
					}
					if (zacinam_pocitat == 1) {
					branch_counter = branch_counter + temp->price;
					}
					
					//printf("value:%d price:%d\n branch_counter:%d\n", temp->value, temp->price, branch_counter);
					neighbour_counter[list_start] --;
				//	printf("neigbour_counter: %d",neighbour_counter[temp->value]);
					neighbour_counter[temp->value] --;
//zkouska noveho					
					opposite_neigh[list_start]++;
					opposite_neigh[temp->value]++;
					
					
					
					visited[list_start] = 1; //ANO, SPRAVNE MUSIM OZNACIT JENOM LIST_START
					if (neighbour_counter[temp->value] == 1) { //tj chci pokracovat dal - ale jeste predtim potrebuju nejak odebrat tamtu hranu
						list_start = temp->value;
						
						if (zacinam_pocitat == 1) {
							zapocitat[temp->value] = 1;
						}
						
					}
					else {
//						printf("%d\n", branch_counter);
						final_price = final_price + branch_counter;
						//tady koncim - prirazuji USED
						if (zacinam_pocitat == 1) {
							zapocitat[temp->value] = 1;
						}
						//NOVE ZMENENO - CHCI, ABY USED BYLO SKUTECNE JEN TO, KAM NECO DOSLO..., s puby to nic neudelalo
						if (zacinam_pocitat == 1) {
							used[temp->value] = 1; //mohlo to i pomoct
						}
						
						break;
					}
					//for (int q=0;q<
					
			}
			//i=0;

		}
	}
//	printf("hupky");
	final_price = final_price*2;
//	fprintf(stderr,"%d\n", final_price);
	
	for (int i=0; i= 2) {
			break;
		}
	}
	
									
	if ((my_used_counter == 1) && (keys[the_used_node] == 1)) {
		//nemusim nic delat, uz to mam zpocteno
		printf("%d\n", final_price);
		return 0;
	}
	
	else if (my_used_counter == 1) { //vsechny jsou ze stejneho, a nekonci to keyem, takze budu muset neco odecist //ZACATEK
		//printf("hup");
		
		int opposite_price = 0;
		//int counter_mine = 0;
while (1) {
		struct node* temp_op = graph->adjLists[the_used_node];
		//if (counter_mine
		
		int one_side_key = -1;
		int other_side_key = -1;
		int little_price = 0;
		
		//NOVE
/*		fprintf(stderr,"visited\n");
		printmatrixchar(all_servers, visited);
		fprintf(stderr,"\n");
		fprintf(stderr,"opposite_neigh\n");
		printmatrixint(all_servers,opposite_neigh); */
		
		
		//MA TO BYT VEVNITR V CYKLU? //SEM MI TO VUBEC NESKOCI - ROZVETVUJE SE TO OD 1.
		if (opposite_neigh[the_used_node] == 1) { //kdyz jdu jen 1 smerem, jsem ok a jdu dokud nenarazim na key
					while((!visited[temp_op->value])) {
		temp_op = temp_op->next;
		}
		
//		fprintf(stderr,"Jsem zpet v teto podmince, spravne");
		
		
		
//			fprintf(stderr,"jsem v 1");
			opposite_price = opposite_price+temp_op->price;	//NEMAM TO NAHODOU PRICIST UZ NAHORE? - MYSLIM, ZE NE
			//pri														
			if (keys[temp_op->value] == 1) {
			//	printf("huraaaaa"); - tak jo, na muj pidiprikladek to funguje...
				//tady to skoncim, dosla jsem ke klici, mam vystarano
				final_price = final_price - (opposite_price*2);

				printf("%d\n", final_price);
				return 0;
			}
			else {
				//bohuzel, musim pokracovat - presunu node a jedu znovu
				the_used_node = temp_op->value;
				//JE PRO ME DULEZITE VISITED, MELA BYCH HO PREPSAT:
				visited[temp_op->value] = 0;															//POZOR NA TO VISITED!, TAKY BYCH MELA ASI SNIZIT POCET SOUSEDU, NE?
				opposite_neigh[the_used_node] --;
				continue;						//ZATIM NEMAM CYKLUS, POTOM ODKOMENTOVAT
			}
		}
		
 //CHYBA JE TADY V TOM ELSE!!!
		else { //kdyz muj node, ve kterem se nachazim, ma vice, nez 1 spojeni - na zacatku mam vzdy najite relevantni, v probehu uz je musim dohledavat!
		//	printf("vice");
			for (int i=0; ivalue])) { //potrebuji to donacist
//						fprintf(stderr,"vysited in %d: %d\n", temp_op->value, visited[temp_op->value]);
					//	fprintf(stderr,"%d\n", temp_op->value);
//						fprintf(stderr,"fakt se mi to kousne tady");
						temp_op = temp_op->next;
//						fprintf(stderr,"neskoci_to sem");
					}
				
//				fprintf(stderr,"vyskocilo to");
				
				if (keys[temp_op->value] == 1) {
				//ukoncim to bez pricteni ceny
					final_price = final_price - (opposite_price*2);
					printf("%d\n", final_price);
					return 0;
				}
				
				
				//bfs from childu... kdyz najdu key, skoncim to a reknu, ze je TO TENHLE TEMP->VALUE a ulozim si one_side_key; - protoze 
//				fprintf(stderr,"temp: %d\n", temp_op->value);
				int ret = bfs(temp_op->value, graph);
				
//				fprintf(stderr, "\ntemp_op: %d RET: %d\n", temp_op->value,ret);

				if (ret != -1) {
//					fprintf(stderr,"juch");
					if (one_side_key == -1) {
//						fprintf(stderr,"jsem tady ikdyz tu nemam byt");
						one_side_key = temp_op->value; //je mi jedno, jake je to key
						little_price = temp_op->price; //pricetla jsem si cenu toho, kam budu pokracovat //nemam vyresene to pokracovani dal
//						fprintf(stderr,"%d", little_price);
					}
					else {
						//ukoncuji bez pricitani
//						fprintf(stderr,"tady to hrapuje");
						final_price = final_price - (opposite_price*2);
						printf("%d\n", final_price);
						return 0;
						//RETURN
					}
				}
				
				//POKUD ONE SIDE KEY NENI -1, A JA MAM POZITIVNI SHODU, UKONCUJI TO... VRACIM VYPOCET CENY
				
				
				//PROHLASUJI TEMP ZA NAVSTIVENY - hodnoty mam ted obracene
				visited[temp_op->value] = 0; //CHAPU TO SPRAVNE, ZE TAM MAM PAK VSUDE NULY A BEHAM DOKOLECKA?
				

				//tady to presunu na dalsi temp, pokud uz to neprobehlo vsechny, co melo
				if (i == opposite_neigh[the_used_node]-1) { //POKUD TO DOBEHLO DO KONCE A NASLO TO POUZE JEDEN KEY SERVER, JINAK BY TO SPRAVNE MELO SKONCIT NA TAMTEN RETURN
//					fprintf(stderr,"\nes\n");
					//POUZE TADY POKRACUJU - STACI, KDYZ TO ODECTU TADY? - MOZNA, KDYZ UZ SE NIKDY NEPODIVAM NAD TO NAD TIM, TAK BY TO STACIT MOHLO, TAMTO MAM OZNACENY JAKO VISITED, TAK BY TO TAM SNAD NEMUSELO LEZT...
					the_used_node = one_side_key;
					opposite_price = opposite_price + little_price; //little price je cena te cesty, kdyz poprve narazim do nejake vetve s keyem, v te dbe jeste nevim, jestli v jinych vetvich na ne nenarazim tez...
					//nove
					opposite_neigh[the_used_node]--;
					break; //KONCIM NE? MUSIM ZKONCIT, ALE NEVIM, PROC BY MI TO CHTELO ZNOVA SKAKAT DO TOHO CYKLU?
					
					
					
					
					//ZKOUSIM ODSTRANIT TEN SPOJ V OPPOSITE NEIGH - PRECI JEN, NEKDE BYCH HO MELA ODTSRANOVAT
					
					//opposite_price = opposite_price+little_price;
					
					//a zaroven potrebuji pricist opposite cenu - vse probehlo dobre a ja pokracuji dal
				} 
				
			/*	else if (ivalue);
				}*/
				
		
	} //for
		}
} //while
	} //KONEC
	
	
	
	for (int i=0; iadjLists[cycle_vertex];
	while((visited[temp2->value])) {
		temp2 = temp2->next;
	}
//	printf("value1: %d", temp2->value);
	temp2 = temp2->next;
	while((visited[temp2->value])) {
		temp2 = temp2->next;
	}
	value2 = temp2->value;
	value2_price = temp2->price;
//	printf("value2: %d", temp2->value);
	
	while (1) {
		if (visited[cycle_vertex] != 0) {
			break;
		}
		struct node* temp = graph->adjLists[cycle_vertex];
//		printf("cycle v: %d\n",cycle_vertex);
		if (cycle_vertex == value2) {
			//PRICTU TU POSLEDNI HRANU - PRICTU VZDY, KDYZ JDU VZDY OD USED
			cur_component = cur_component+value2_price;
//			printf("\ncur:comp: %d\n", cur_component);
			break;
		}
		while((visited[temp->value])) { //likviduji predchozi spoje
			temp = temp->next;
		}
		cycle_price = cycle_price+temp->price;
		cur_component = cur_component + temp->price;
		if (cur_component>biggest_component) {
			biggest_component = cur_component;
		}
		if (stav_8 == 0) {
			if (used[temp->value] == 1) { //prerusuji komponentu a zacinam novou
				//printf("\ncur:comp: %d\n", cur_component);
				cur_component = 0;
			}
		}
		if (stav_8 != 0) {
			if (keys[temp->value] == 1) {
				cur_component = 0;
			}
		}
//		printf("%d\n", cycle_price);
		visited[cycle_vertex] = 1;
		cycle_vertex = temp->value;
	} 
	cycle_price = cycle_price+value2_price;
	//fprintf(stderr, "FINAL CYCLE PRICE> %d\n", cycle_price);
	
	
	if (cur_component>biggest_component) {
		biggest_component = cur_component;
	}
	
	
	//zkousim ostetrit 8 - TENHLE VYPOCET ASI NEMUZU POUZIT :/
/*	if (final_price == 0) {
		done_price = cycle_price - biggest_component*2;
	}*/
	
//	printf("biggest_compo: %d\n", biggest_component);
	if ((biggest_component*2) > cycle_price) {
		//delam prvni vypocet
		done_price = final_price + cycle_price - ((biggest_component*2)-cycle_price);
	}
	else {
		//delam druhy vypocet - prictu cely cyklus
//		printf("nastava");
		done_price = final_price + cycle_price;
		
	}
	printf("%d\n", done_price);
	//return 0;
	

/*	for (int q=0; qadjLists[i];  
		    while (temp)
		    {
		    	once = 1;
		    	if (neigbour_counter == 0) {
		    		neigbour_one = temp->value;
		    	}
		    	else {
		    		neigbour_two = temp->value;
		    	}
		    	if (neigbour_counter >= 2) { //zkousim, jestli ma presne sousedy
		    	 	wrong = 1;
		    		break;}
		    	neigbour_counter++;
		    	temp = temp->next;
		    }
	    if (neigbour_two == 0) {wrong = 1;}
	    if (wrong != 1) { //zkousim, zda sousedi maji stejny pocet sousedu
	    	int n1 = 0;
	    	int n2 = 0;
	    	struct node* neigbour1 = graph->adjLists[neigbour_one];
	    	struct node* neigbour2 = graph->adjLists[neigbour_two];
	    	
	    	while (neigbour1) {
	    		n1++;
	    		neigbour1 = neigbour1->next;
	    	}
	    	while (neigbour2) {
	    		n2++;
	    		neigbour2 = neigbour2->next;
	    		if (n2>n1) {
	    			wrong = 1;
	    			break;
	    		}
	    	}
	    	if ((n1 == n2) && (wrong == 0) && (once == 1)) {
	    		//mozny soket, zacnu z nej bfs
	    		bfs(i, graph);
	    	}  	
	    }
	}
	
	free(visited);
	free(used);
	free(queue);
	free(side);
	free(done_socket);
	
*/
	//free(graph);
  clock_t end = clock();
    float seconds = (float)(end - start) / CLOCKS_PER_SEC;
//    printf("\n%f\n", seconds);

//	freeGraph(graph, all_servers);
	free(help_visited);
	free(visited);
	free(used);
	free(queue);
	free(neighbour_counter);
	free(opposite_neigh);
	free(zapocitat);
	return 0;
}

===== 3. nejrychlejší v C/C++ =====


#include 
#include 
#include 
#include 
#include 

typedef struct Node {
    int hodnota;
    int cena;
    struct Node* next;
} Node_t;

typedef struct PomocnaPole {
    int* poleSousedu;
    int* uzProjite;
    bool* byvalaKrizovatka;
    int* poleCenUzlu;
    int* sumaServeruVNodech;
} pomoc_t;

typedef struct Pole {
    struct Node *pocatekPole;
}  Pole_t;

typedef struct Graf {
    int pocetUzlu;
    struct Pole* pole;
} Grafik_t;



Grafik_t* udelejGrafa (int pocetUzlu) {
    Grafik_t* Graf = (Grafik_t*) malloc (1 * sizeof(Grafik_t));
    Graf->pocetUzlu = pocetUzlu;
    Graf->pole = (Pole_t*) malloc (pocetUzlu * sizeof(Pole_t));
    int i = 0;
    while (i < pocetUzlu) {
        Graf->pole[i].pocatekPole = NULL;
        i = i + 1;
    }
    return Graf;
}

pomoc_t* pomocPole;

int najdiSousedyProsim (int i, Grafik_t* Graf) {
    int sum = 0;
    Node_t *uzel = Graf->pole[i].pocatekPole;
    while (uzel != NULL) {
      //  if (pomocPole->uzProjite[uzel->hodnota]<=0) {
            sum++;
       // }

        uzel = uzel->next;
    }
    return sum;
}

void pridejUzlik (Grafik_t* Graf, int uzel1, int uzel2, int cena, int kolik) {
    Node_t* novyUzel = (Node_t*) malloc (1 * sizeof(Node_t));
    Node_t* novyUzel2 = (Node_t*) malloc (1 * sizeof(Node_t));

    novyUzel->hodnota = uzel2;
    novyUzel->cena = cena;
    novyUzel2->hodnota = uzel1;
    novyUzel2->cena = cena;

    novyUzel->next = Graf->pole[uzel1].pocatekPole;
    Graf->pole[uzel1].pocatekPole = novyUzel;

    novyUzel2->next = Graf->pole[uzel2].pocatekPole;
    Graf->pole[uzel2].pocatekPole = novyUzel2;
}

unsigned char* KS;
int numberKS = 0;
bool cenaJe = 0;
int kruznice = -13, sumaKSveVetvicce = 0;
int celkovaCena = 0, cenaKolem = 0;
char prvni = 1;
int nejCenaKruzCesty = 0, cenaZatimSpoctena = 0;
int soucetVetvi = 0;


int main () {
    int numberOfNodes, numberOfKS;
    scanf("%d %d", &numberOfNodes, &numberOfKS);

     pomocPole = (pomoc_t*) malloc(1 * sizeof(pomoc_t));

    // memsetovat a malloc
    KS = (unsigned char*) malloc (sizeof(unsigned char)*  numberOfNodes);
    memset( KS, 0, sizeof( KS));
    pomocPole->poleSousedu = (int*) malloc (sizeof(int)*  numberOfNodes);
    memset( pomocPole->poleSousedu, 0, sizeof(pomocPole->poleSousedu));
    pomocPole->byvalaKrizovatka = (bool*) malloc (sizeof(bool)*  numberOfNodes);
    memset(pomocPole->byvalaKrizovatka, 0, sizeof(pomocPole->byvalaKrizovatka));


    Grafik_t* Graf = udelejGrafa (numberOfNodes);

    int prvniN, druhy, cena;
    for (int n = 0; n < numberOfNodes; n++) {
        scanf("%d %d %d", &prvniN, &druhy, &cena);
        pridejUzlik (Graf, prvniN, druhy, cena, n);
        pomocPole->poleSousedu[prvniN]++;
        pomocPole->poleSousedu[druhy]++;
    }
    int pozice;
    for (int i = 0; i < numberOfKS; i++) {
        scanf("%i", &pozice);
        KS[pozice] = 1;
    }

    pomocPole->uzProjite = (int*) malloc (sizeof(int)*  numberOfNodes);
    memset(pomocPole->uzProjite, 0, sizeof(pomocPole->uzProjite));
    pomocPole->poleCenUzlu = (int*) malloc (sizeof(int) * numberOfNodes);

    for (int i = 0; i < numberOfNodes; i++) {
        pomocPole->poleCenUzlu[i] = 0;
    }

    pomocPole->sumaServeruVNodech = (int*) malloc (sizeof(int)*  numberOfNodes);
    memset(pomocPole->sumaServeruVNodech, 0, sizeof(pomocPole->sumaServeruVNodech));


    for (int k = 0; k < numberOfNodes; k++) {

        if (najdiSousedyProsim(k, Graf) == 1) {
            sumaKSveVetvicce = 0;
            pomocPole->uzProjite[k]=1;
            int prohledavanyUzlik = Graf->pole[k].pocatekPole->hodnota;
            bool zacniPocitatCenu = false;
            int prubeznaSumaCeny = 0;

            if (KS[k] == 1) { // list je KS
                zacniPocitatCenu = true;
                sumaKSveVetvicce++;
                prubeznaSumaCeny += Graf->pole[k].pocatekPole->cena;
            }

            for (int ba = 0; ba < numberOfNodes; ba++) {

                if (pomocPole->poleSousedu[prohledavanyUzlik] != 2){
                    break;
                }
                pomocPole->uzProjite[prohledavanyUzlik] = 1;

                if (pomocPole->byvalaKrizovatka[prohledavanyUzlik] == true || KS[prohledavanyUzlik] == 1) {
                    prubeznaSumaCeny = prubeznaSumaCeny + pomocPole->poleCenUzlu[prohledavanyUzlik];
                    zacniPocitatCenu = true;
                    sumaKSveVetvicce = sumaKSveVetvicce + (pomocPole->byvalaKrizovatka[prohledavanyUzlik] == true ? pomocPole->sumaServeruVNodech[prohledavanyUzlik]: 1);
                }

                if (sumaKSveVetvicce == numberOfKS) {
                    printf("%d", prubeznaSumaCeny * 2);
                    return 0;
                }

                Node_t *soucasnyUzlik = Graf->pole[prohledavanyUzlik].pocatekPole;

                for (int ble = 0; ble < numberOfNodes; ble++) {
                    if (pomocPole->uzProjite[soucasnyUzlik->hodnota] != 1) {
                        break;
                    }
                    soucasnyUzlik = soucasnyUzlik->next;
                    ble=0;
                }
                prubeznaSumaCeny = prubeznaSumaCeny + (zacniPocitatCenu == true ? soucasnyUzlik->cena : 0);
                prohledavanyUzlik = soucasnyUzlik->hodnota;
                ba=0;
            }

            pomocPole->byvalaKrizovatka[prohledavanyUzlik] = prubeznaSumaCeny > 0 ? true : pomocPole->byvalaKrizovatka[prohledavanyUzlik];

            pomocPole->poleSousedu[prohledavanyUzlik]--;
            pomocPole->poleCenUzlu[prohledavanyUzlik] = pomocPole->poleCenUzlu[prohledavanyUzlik] + prubeznaSumaCeny;
            pomocPole->sumaServeruVNodech[prohledavanyUzlik] = pomocPole->sumaServeruVNodech[prohledavanyUzlik] + sumaKSveVetvicce;

            // do kruznice nendu
            if (pomocPole->sumaServeruVNodech[prohledavanyUzlik] == numberOfKS) {
                int resultik0 = pomocPole->poleCenUzlu[prohledavanyUzlik] + pomocPole->poleCenUzlu[prohledavanyUzlik];
                printf("%ld", resultik0);
                return 0;
            }

            if (zacniPocitatCenu == true){
                kruznice = prohledavanyUzlik;
            }
        }
    }

    //spocti cenu loopu
    if (kruznice == -13){ // kdyz nebyla nastavena kruznice
        for (int i = 0; i < numberOfNodes; i++) {
            if (KS[i] == 1){   // nastav kruznici na key server
                kruznice=i;
            }
        }
    }

    int pocatekCesty = kruznice;
    pomocPole->uzProjite[kruznice] = 13;

    //projdem kruznici
    for (int i = 0; i <= numberOfNodes; i++) {

        Node_t *prochazeny = Graf->pole[pocatekCesty].pocatekPole;

        for (int y = 0; y <= numberOfNodes; y++) {
            if(prochazeny->hodnota >numberOfNodes || prochazeny->hodnota < 0){
                //printf("sakra");
            }
            if (pomocPole->uzProjite[prochazeny->hodnota] <= 0){
                break;
            }
            if (pomocPole->uzProjite[prochazeny->hodnota]> 7 && prvni == 0){

                cenaKolem = cenaKolem + prochazeny->cena;
                cenaZatimSpoctena = cenaZatimSpoctena + prochazeny->cena;

                nejCenaKruzCesty = nejCenaKruzCesty < cenaZatimSpoctena ? cenaZatimSpoctena : nejCenaKruzCesty;

                soucetVetvi = soucetVetvi + pomocPole->poleCenUzlu[prochazeny->hodnota];

                if (cenaKolem < (cenaKolem-nejCenaKruzCesty) * 2){
                    long int resultik = cenaKolem + soucetVetvi + soucetVetvi;
                    printf("%ld", resultik);
                } else {
                    long int resultik2 = soucetVetvi + soucetVetvi + 2 * (cenaKolem- nejCenaKruzCesty);
                    printf("%ld", resultik2);
                }
                return 0;
            }
            prochazeny = prochazeny->next;
        }

        cenaKolem += prochazeny->cena;
        cenaZatimSpoctena += prochazeny->cena;

        prvni = prvni == 1 ? -13 : 0;
        pomocPole->uzProjite[pocatekCesty] = pomocPole->uzProjite[pocatekCesty] + 1;
        pocatekCesty = prochazeny->hodnota;
        soucetVetvi = soucetVetvi + pomocPole->poleCenUzlu[pocatekCesty];

        int temp = nejCenaKruzCesty;
        
        nejCenaKruzCesty = (KS[pocatekCesty] > 0 || pomocPole->poleCenUzlu[pocatekCesty]) > 0? (nejCenaKruzCesty < cenaZatimSpoctena ? cenaZatimSpoctena : nejCenaKruzCesty) : nejCenaKruzCesty;
        nejCenaKruzCesty = pomocPole->poleCenUzlu[pocatekCesty] > 0 ? (nejCenaKruzCesty = nejCenaKruzCesty < cenaZatimSpoctena ? cenaZatimSpoctena : nejCenaKruzCesty) : nejCenaKruzCesty;

        if (nejCenaKruzCesty != temp){
            cenaZatimSpoctena = 0;
        }
        if (pomocPole->poleCenUzlu[pocatekCesty] > 0) {
            nejCenaKruzCesty = nejCenaKruzCesty < cenaZatimSpoctena ? cenaZatimSpoctena : nejCenaKruzCesty;
            cenaZatimSpoctena = 0;
        }
        i = 0;
    }
}

===== 1. nejrychlejší v Javě =====



package alg;

public class Spojeni {
    int kam;
    int cena;
    Spojeni paroveSpojeni;

    public Spojeni(int kam, int cena) {
        this.kam = kam;
        this.cena = cena;
    }
}

package alg;

import java.io.IOException;
import java.util.ArrayList;


public class Main {
    private InputReader ir = new InputReader();
    private int N;
    private int K;
    
    /* NODE */
    private boolean[] jeDulezity;
    private boolean[] jeNodeNavstiven;
    private boolean[] jeNodeKlic;   
    private int[] aktualniCena;
    private int celkovaCenaVetvi = 0;
    private int celkovaCenaCyklu = 0; 
    private ArrayList[] spojeni;
    
    /* CYKLUS */
    private int startovniNode;
    private int pocetNoduVCyklu = 0;
    
    
    public void nactiVstup() throws IOException{
        N = ir.nextInt();
        K = ir.nextInt();
        aktualniCena = new int[N];
        jeNodeNavstiven = new boolean[N];
        jeNodeKlic = new boolean[N];
        jeDulezity = new boolean[N];
        spojeni = new ArrayList[N];
        
        for (int i = 0; i < N; i++) {
            spojeni[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            int levyNode = ir.nextInt();
            int pravyNode = ir.nextInt();
            int cenaSpojeni = ir.nextInt();

            Spojeni praveSpojeni = new Spojeni(pravyNode, cenaSpojeni);
            Spojeni leveSpojeni = new Spojeni(levyNode, cenaSpojeni);

            praveSpojeni.paroveSpojeni = leveSpojeni;
            leveSpojeni.paroveSpojeni = praveSpojeni;

            spojeni[levyNode].add(praveSpojeni);
            spojeni[pravyNode].add(leveSpojeni);
        }

        for (int i = 0; i < K; i++) {
            int klic = ir.nextInt();
            jeNodeKlic[klic] = true;
            jeDulezity[klic] = true;
        }
    }
    
    public boolean odstrihniVetve(){     
        boolean preruseniCyklu = true;
        int pocetKlicuVeVetvich = 0;
        while (preruseniCyklu) {
            preruseniCyklu = false;
            for (int i = 0; i < N; i++) {
                int index = i;
                while (!jeNodeNavstiven[index] && spojeni[index].size() == 1) {
                    preruseniCyklu = true;
                    jeNodeNavstiven[index] = true;
                    Spojeni noveSpojeni = spojeni[index].get(0);
                    if (jeNodeKlic[index]) {
                        pocetKlicuVeVetvich++;
                        if (K == 1000 && pocetKlicuVeVetvich == K) {
                            celkovaCenaVetvi = aktualniCena[index] * 2;
                            return false;
                        }
                    }
                    if (jeDulezity[index]) {
                        aktualniCena[noveSpojeni.kam] += aktualniCena[index] + noveSpojeni.cena;
                        jeDulezity[noveSpojeni.kam] = true;
                    }
                    spojeni[index].remove(noveSpojeni);
                    spojeni[noveSpojeni.kam].remove(noveSpojeni.paroveSpojeni);
                    index = noveSpojeni.kam;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            if (spojeni[i].size() != 2) {
                continue;
            }
            if (jeDulezity[i]) {
                startovniNode = i;
                pocetNoduVCyklu++;
            }
            celkovaCenaVetvi += aktualniCena[i];
        }
        celkovaCenaVetvi *= 2;
        return true;
    }
    
    public void vyresKruznici(){
        int docasnaCena = 0;
        int[] docasnaCenaCyklu = new int[pocetNoduVCyklu + 1];
        int aktualniNode = startovniNode;
        int index = 1;
        int CenaCelehoCyklu;
        int posledniNode;
        int cena;
        while (spojeni[aktualniNode].size() > 0) {
            Spojeni noveSpojeni = spojeni[aktualniNode].get(0);
            docasnaCena += noveSpojeni.cena;
            if (jeDulezity[noveSpojeni.kam]) {
                docasnaCenaCyklu[index] = docasnaCena;
                index++;
            }
            spojeni[aktualniNode].remove(noveSpojeni);
            spojeni[noveSpojeni.kam].remove(noveSpojeni.paroveSpojeni);
            aktualniNode = noveSpojeni.kam;
        }
        CenaCelehoCyklu = docasnaCenaCyklu[pocetNoduVCyklu];
        celkovaCenaCyklu = docasnaCenaCyklu[pocetNoduVCyklu];
        for (int i = 0; i < pocetNoduVCyklu; i++) {
            posledniNode = (i + pocetNoduVCyklu - 1) % pocetNoduVCyklu;
            cena = docasnaCenaCyklu[posledniNode] - docasnaCenaCyklu[i];
            if (cena < 0) {
                cena += CenaCelehoCyklu;
            }
            cena *= 2;
            if (cena < celkovaCenaCyklu) {
                celkovaCenaCyklu = cena;
            }
        }
    }
    public void Vysledek() {
         System.out.println(celkovaCenaVetvi + celkovaCenaCyklu);
    }
    
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.nactiVstup();
        if (main.odstrihniVetve()) {
            main.vyresKruznici();
        }
        main.Vysledek();    
    }
}

===== 2. nejrychlejší v Javě =====


package alg;

public class Connection {

    int to, cost;
    Connection pairConnection;

    public Connection(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}

package alg;

import java.io.IOException;
import java.util.ArrayList;

public class Main {

    private InputReader ir = new InputReader();

    private int N, K;

    //node replacement
    private boolean isUnvisited[];
    private boolean isKeyServer[];
    private boolean isImportant[];
    private int actualValue[];

    private ArrayList connections[];


    private int sumOfBranches = 0, sumOfCircle = 0;

    //circle things
    private int startNode;
    private int numOfNeededCircleNodes = 0;


    public void loadData() throws IOException {
        N = ir.nextInt();
        K = ir.nextInt();

        isUnvisited = new boolean[N];
        isKeyServer = new boolean[N];
        isImportant = new boolean[N];
        actualValue = new int[N];

        connections = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            connections[i] = new ArrayList<>();
            isUnvisited[i] = true;
        }


        for (int i = 0; i < N; i++) {

            int leftIndex = ir.nextInt();
            int rightIndex = ir.nextInt();
            int cost = ir.nextInt();

            Connection con1 = new Connection(rightIndex, cost);
            Connection con2 = new Connection(leftIndex, cost);

            con1.pairConnection = con2;
            con2.pairConnection = con1;

            connections[leftIndex].add(con1);
            connections[rightIndex].add(con2);
        }

        for (int i = 0; i < K; i++) {
            int index = ir.nextInt();
            isKeyServer[index] = true;
            isImportant[index] = true;
        }

    }


    public boolean cutBranches() {

        int numOfKeysInBranches = 0;


        boolean change = true;

        while (change) {
            change = false;
            for (int idx = 0; idx < N; idx++) {
                int i = idx;
                while (isUnvisited[i] && connections[i].size() == 1) {
                    change = true;

                    isUnvisited[i] = false;

                    Connection conn = connections[i].get(0);

                    if (isKeyServer[i]) {
                        numOfKeysInBranches++;

                        if (numOfKeysInBranches == K && K == 1000) {
                            sumOfBranches = actualValue[i] * 2;
                            return false;
                        }

                    }

                    if (isImportant[i]) {
                        actualValue[conn.to] += actualValue[i] + conn.cost;
                        isImportant[conn.to] = true;
                    }

                    connections[i].remove(conn);
                    connections[conn.to].remove(conn.pairConnection);

                    i = conn.to;
                }
            }
        }

        for (int i = 0; i < N; i++) {

            if (connections[i].size() != 2) {
                continue;
            }

            if (isImportant[i]) {
                startNode = i;
                numOfNeededCircleNodes++;
            }
            sumOfBranches += actualValue[i];
        }
        sumOfBranches *= 2;
        return true;
    }


    public void doCircle() {

        int tempSum = 0;
        int tempCircleSum[] = new int[numOfNeededCircleNodes + 1];

        int actNode = startNode;
        int neededIndex = 1;
        while (connections[actNode].size() > 0) {

            Connection conn = connections[actNode].get(0);

            tempSum += conn.cost;
            if (isImportant[conn.to]) {
                tempCircleSum[neededIndex] = tempSum;
                neededIndex++;
            }

            connections[actNode].remove(conn);
            connections[conn.to].remove(conn.pairConnection);

            actNode = conn.to;
        }

        int wholeCircle = tempCircleSum[numOfNeededCircleNodes];
        sumOfCircle = tempCircleSum[numOfNeededCircleNodes];

        //nyni vyuziju vysledky
        for (int i = 0; i < numOfNeededCircleNodes; i++) {

            int endIndex = (i + numOfNeededCircleNodes - 1) % numOfNeededCircleNodes;
            int cost = tempCircleSum[endIndex] - tempCircleSum[i];
            if (cost < 0) {
                cost += wholeCircle;
            }
            cost *= 2;
            if (cost < sumOfCircle) {
                sumOfCircle = cost;
            }
        }
    }

    public int computeFinalResult() {
        return sumOfBranches + sumOfCircle;
    }

    public static void main(String[] args) throws IOException {
        Main m = new Main();

        m.loadData();
        boolean ret = m.cutBranches();
        if (ret)
            m.doCircle();
        System.out.println(m.computeFinalResult());

    }
}

===== 3. nejrychlejší v Javě =====


package alg;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.*;

/**
 *
 */
public class Main {

    private static final Scanner s = new Scanner(System.in);
    private static int nextInt() {
        return Integer.parseInt(s.next());
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }


    private static class ConnectionArray {

        private Connection[] backing;
        private int used = 0;

        public ConnectionArray(int initialCapacity) {
            backing = new Connection[initialCapacity];
        }

        public void add(Connection num) {
            if (used == backing.length) {
                Connection[] bigger = new Connection[backing.length * 2];
                System.arraycopy(backing, 0, bigger, 0, used);
                backing = bigger;
            }
            backing[used++] = num;
        }

        public Connection get(int i) {
            return backing[i];
        }

        public boolean contains(Connection num) {
            for (int i = 0; i < used; i++) {
                if (backing[i] == num) return true;
            }
            return false;
        }

        public boolean remove(int node) {
            for (int i = 0; i < used; i++) {
                if (backing[i].node == node) {
                    backing[i] = backing[--used];
                    return true;
                }
            }
            return false;
        }

        public int size() {
            return used;
        }

        public void clear() {
            used = 0;
        }
    }

    private static class Connection {
        public final int node;
        public final int cost;

        public Connection(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        @Override
        public int hashCode() {
            return node * 613 + cost * 809;
        }

        @Override
        public boolean equals(Object obj) {
            return obj != null && obj instanceof Connection && ((Connection) obj).node == node;
        }
    }

    private static TreeSet keyServers = new TreeSet<>();
    private static final ArrayList connections = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        long timeSinceLastCheckpoint = System.currentTimeMillis();

        final Reader s = new Reader();

        final int serverCount = s.nextInt();
        final int keyServCount = s.nextInt();

        connections.ensureCapacity(serverCount);
        for (int i = 0; i < serverCount; i++) {
            connections.add(new ConnectionArray(70));
        }

        for (int i = 0; i < serverCount; i++) {
            final int nodeA = s.nextInt();
            final int nodeB = s.nextInt();
            final int edgeCost = s.nextInt();

            connections.get(nodeA).add(new Connection(nodeB, edgeCost));
            connections.get(nodeB).add(new Connection(nodeA, edgeCost));
        }

        for (int i = 0; i < keyServCount; i++) {
            final int keyServId = s.nextInt();
            keyServers.add(keyServId);
        }

        if (keyServers.size() <= 1) {
            System.out.println(0);
            return;
        }

        System.err.println("[" + (System.currentTimeMillis() - timeSinceLastCheckpoint) / 1000f + "s] Loaded"); timeSinceLastCheckpoint = System.currentTimeMillis();

        int treeCost = 0;
        int node;
        for (int i = 0; i < connections.size(); i++) {
            if (connections.get(i).size() != 1) continue;
            node = i;
            boolean keyServPath = false;
            while (connections.get(node).size() == 1) {
                final ConnectionArray cons = connections.get(node);
                final Connection c = connections.get(node).get(0);
                for (int j = 0; j < cons.size(); j++) if (cons.get(j).node == node) {
                    cons.remove(j);
                    break;
                }

                connections.get(c.node).remove(node);
                connections.get(node).clear();

                if (keyServers.remove(node)) keyServPath = true;

                if (keyServers.size() == 0) {
                    System.out.println(treeCost * 2);
                    System.err.println("[" + (System.currentTimeMillis() - timeSinceLastCheckpoint) / 1000f + "s] Tree cost: " + treeCost + ", no cycle"); timeSinceLastCheckpoint = System.currentTimeMillis();
                    return;
                }
                if (keyServPath) {
                    treeCost += c.cost;
                }

                node = c.node;
            }
            if (keyServPath) {
                keyServers.add(node);
            }
        }

        System.err.println("[" + (System.currentTimeMillis() - timeSinceLastCheckpoint) / 1000f + "s] Cycle isolated,  tree cost: " + treeCost); timeSinceLastCheckpoint = System.currentTimeMillis();

        int cycleNextNode, cycleLastNode;
        final int prices[] = new int[keyServers.size()];
        int priceI = 0;
        int edgeCost = 0;
        int fullCost = 0;

        for (int i = 0; i < connections.size(); i++) {
            if (connections.get(i).size() == 2 && keyServers.contains(i)) {
                cycleNextNode = i;
                cycleLastNode = connections.get(i).get(0).node;

                do {
                    final ConnectionArray c = connections.get(cycleNextNode);
                    final int next = c.get(0).node == cycleLastNode ? c.get(1).node : c.get(0).node;
                    edgeCost += c.get(0).node == cycleLastNode ? c.get(1).cost : c.get(0).cost;
                    cycleLastNode = cycleNextNode;
                    cycleNextNode = next;

                    if (keyServers.contains(cycleNextNode)) {
                        prices[priceI++] = edgeCost;
                        fullCost += edgeCost;
                        edgeCost = 0;
                    }
                } while (cycleNextNode != i);
                break;
            }
        }

        int bestCycleCost = fullCost;
        for (int price : prices) {
            if ((fullCost - price) * 2 < bestCycleCost) bestCycleCost = (fullCost - price) * 2;
        }



        System.err.println("[" + (System.currentTimeMillis() - timeSinceLastCheckpoint) / 1000f + "s] Inner cycle cost: " + bestCycleCost); timeSinceLastCheckpoint = System.currentTimeMillis();
        System.out.println(treeCost * 2 + bestCycleCost);

    }
}