Key Servers

zadání

Kódy nejrychlejších řešení viz níže.

Relativní čas vůči referenčnímu řešení se počítá tak, že se sečtou v posledním odevzdaném studentském řešení všechny časy na neveřejných souborech ( časStud ), všechny časy na na neveřejných souborech v referenčním řešení ( časRef ) a spočte se podíl časStud/časRef. Zveřejňujeme pouze časy řešitelů, kteří dosáhli na 10/10. Časy řešení v některých instancích pomalých nebo chybných pravděpodobně nejsou směrodatné.

řešitel     jazyk      relativní čas vůči referenčnímu řešení 
 
skalaja7     Cpp | 10  0.145 
preister       C | 10  0.168 
krivapa2       C | 10  0.174 
klimema4       C | 10  0.179 
lebeddar       C | 10  0.197 
konicsim       C | 10  0.201 
mertahan       C | 10  0.205 
nollhyne       C | 10  0.212 
novotvo8       C | 10  0.220 
pultami1     Cpp | 10  0.223 
krouppe2       C | 10  0.228 
neckavit     Cpp | 10  0.249 
dedkoba1     Cpp | 10  0.250 
kacenjir       C | 10  0.252 
jakeskla       C | 10  0.270 
skoreja5       C | 10  0.270 
brejcka1     Cpp | 10  0.285 
voracva1     Cpp | 10  0.288 
hrubype7     Cpp | 10  0.296 
glingvla       C | 10  0.325 
nejtejan     Cpp | 10  0.334 
jakouto3     Cpp | 10  0.339 
klanjan      Cpp | 10  0.341 
brezipat     Cpp | 10  0.348 
filomich     Cpp | 10  0.353 
sustemar     Cpp | 10  0.356 
repamart       C | 10  0.361 
stoklji1     Cpp | 10  0.368 
manousim     Cpp | 10  0.378 
hvezdmic     Cpp | 10  0.398 
janatpa3     Cpp | 10  0.406 
cernypro     Cpp | 10  0.413 
buitiepq     Cpp | 10  0.580 
ivashmak     Cpp | 10  0.648 
svehlja7    Java | 10  0.854 
trnkavla    Java | 10  0.873 
jirmaja1    Java | 10  1.144 
filipcsa    Java | 10  1.270 
turynmar    Java | 10  1.456 
ottastep    Java | 10  1.466 

#include <vector>
#include <cstdio>
#include <stack>
#include <cstdlib>
 
#ifdef WIN32
 
int getchar_unlocked() { return getchar(); }
 
#elif UNIX
/* Do linux stuff */
#endif
 
using namespace std;
 
struct edge;
 
typedef struct node {
    int id;
    vector<edge> 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<node_t *> nodes(static_cast<unsigned int>(edges_count));
    vector<node_t *> 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<node_t *> 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;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
 
//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; i<rows;i++){
        printf("%i ",arr[i]);
    }
    printf("\n");
}
 void printmatrixint(int rows, int* arr){
    for(int i =0; i<rows;i++){
        printf("%i ",arr[i]);
    }
    printf("\n");
}
 
 
//pridani hran 
void addEdge(struct Graph* graph, int src, int dest, int val, int edge) {
    //pridavam hranu z prvniho prvku do druheho
    struct node* newNode = 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;
}
 
/*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; i<all_servers; i++) { //resi mi spravne levo a pravo, jinak byly problemy s 0
 			queue[i] = -1;
 		} 
 		bfs_count =1;
 	}		
 	else { 
 		for (int i=0; i<all_servers; i++) {
 			queue[i] = -1;
 		//	used[i] = 0;
 		//	visited[i] = 0;
 		}  	
 	}
    help_visited[v] = 0;
    //used[v] = 1;
    queue[rear] = v;
 
    rear++; //konec
    while (rear != front) {//dokud fronta neni plna/prazdna
    	int u = queue[front]; //prvni prvek, ktery byl zvolen
//    	fprintf(stderr,"%d\n", u);
       // used[u] = 1;
        front++;
     //   printf("juch");
        struct node* temp = graph->adjLists[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; i<key_servers; i++) {
		scanf("%d", &key_serv); //pak jeste neco budu muset delat s tim polem
		//printf("key: %d\n", key_serv);
		keys[key_serv] = 1;
		//bfs(key_serv, graph); //TO BFS JAKO TAKOVY FUNGUJE, JEN JA TO DIVNE PROCHAZIM
	}
 
 
 
	for (int i=0; i<all_servers; i++) {
				//zacnu od nej prochazet po rozcesti - po nekoho, kdo ma 3 sousedy, jestli to spravne chapu...
		if (neighbour_counter[i] == 1) {
			int list_start = i;
			int branch_counter = 0;
			int zacinam_pocitat = 0;
			while (1) {
 
				struct node* temp = graph->adjLists[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<all_servers; i++) {	//ZAS KDYBY TO NEFUNGOVALO, JAK TO, ZE TOHLE VSE JE 2?
		 if (neighbour_counter[i] == 1) {
		 //	printf("VITEZSTVI!");
		 //	printf("%d", neighbour_counter[i]);
		 }
	}
 
 
 
	int cycle_price = 0;
	int prvni = -1;
	int prvni_smycka = 0;
	int cycle_vertex = 0;
	int value2;
	int value2_price = 0;
 
	int cur_component=0;
	int biggest_component=0;
	int done_price = 0;
 
	int stav_8 = 0;
 
	//SNAZIM SE PREDEJIT TOMU, ZE VSE JE V JEDNE VETVI - TIM PADEM, KDYZ USED JE JEN JEDEN
	int used_counter = 0;	
 
	//nove reseni 10
	int my_used_counter = 0;
	int the_used_node = 0;
	for (int i=0; i<all_servers;i++) {
		if ((used[i] !=0) && (neighbour_counter[i] !=0)) {
			my_used_counter++;
			//bfs(i, graph);
			//return 0;
			the_used_node = i;
			//printf("juchuuuu\n");
		}
		if (my_used_counter >= 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; i<opposite_neigh[the_used_node];i++) {
//				fprintf(stderr,"vice");
//				fprintf(stderr,"I index: %d\n", i);
 
//					fprintf(stderr,"CUR NODE: %d", the_used_node);
				//	fprintf(stderr,"vsited in 2: %d", visited[2]); //OCITLA JSEM SE TU MOCKRAT
					while((!visited[temp_op->value])) { //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 (i<opposite_neigh[the_used_node]-1) {
					printf("\nno\n");
 
					printf("%d\n", temp_op->value);
				}*/
 
 
	} //for
		}
} //while
	} //KONEC
 
 
 
	for (int i=0; i<all_servers;i++) {
		if((neighbour_counter[i] != 0) && (used[i] != 0))  { //tvari se to, ze je tam vzdycky aspon 1 vetev, kdyztak pridej podminku, tim padem vzdycky bezim od used
			cycle_vertex = i;
			used_counter++; //TOU PODMINKOU VYLOUCIM, - MAM TAM SPOUSTU USU, ALE ZAJIMAJ ME JEN TY V KRUHU
			//MELO BY BYT JEDNO, JESTLI TO BEZIM OD 1. NEBO DRUHEHO NALEZENEHO, NE?
			if (used_counter == 2) {
		//	printf("cycle: %d\n", cycle_vertex); 
				break;
			}
		//	return 0;
		}
		//SNAHA O OSETRENI, KDYZ VE VETVICH NENI ZADNY KLICOVY SERVER - ABY TO OD NECEHO ZACLO BEZET
		if ((i==all_servers-1) && (used_counter == 0)) { //tzn. ze z zadne vetve nic neprislo, ne?  //SEM BY MI TO MELO SKOCIT POUZE, POKUD JE TO NULA
			for (int q=0;q<all_servers;q++) {
				if ((neighbour_counter[q] != 0) && (keys[q] == 1)) { //chci bezet od klice - komponenty ted nedelam pomoci used/neused, ale podle klice
					cycle_vertex = q;
					stav_8 = 1;
 
					break;
 
				}
			}
		}
	}
 
	if (used_counter == 1) {
		printf("%d\n", final_price);
		return 0;
	}
 
	struct node* temp2 = graph->adjLists[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; q<key_servers; q++) {
		if (neigbour_counter[q] == key_servers-1) {
			printf("%d ", neigbour_counter[q]);
		}
	}*/
/*
	for (int i=1; i<nodes;i++) {
		if (done == 1) {
			break;
		}
		int neigbour_counter = 0;
		int wrong = 0;
		int once = 0;
		int neigbour_one = 0;
		int neigbour_two = 0;
		struct node* temp = graph->adjLists[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;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <unistd.h>
 
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;
    }
}

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>[] 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();    
    }
}

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<Connection> 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());
 
    }
}

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<Integer> keyServers = new TreeSet<>();
    private static final ArrayList<ConnectionArray> 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);
 
    }
}