Statistiky serverů

Skupina serverů je navzájem propojena do sítě se stromovou topologií. Některé servery jsou označené jako klíčové. Je zapotřebí shromáždit statistiky provozu klíčových serverů. Shromažďování statistik probíhá následujícím způsobem.
Klíčový server s nejnižším číslem sestaví zprávu a k ní připojí statistiku svého provozu. Potom zprávu vyšle některému z dalších klíčových serverů. Každý klíčový server, který obdrží zprávu, připojí ke zprávě svou statistiku a vyšle zprávu některému dalšímu klíčovému serveru, který ještě zprávu neobržel. Poslední klíčový server, který obdrží zprávu, po připojení statistiky svého provozu vyšle zprávu zpět tomu serveru, který ji vyslal jako první. Zpráva na své cestě mezi dvěma klíčovými servery může přecházet přes další klíčové servery, je však vždy zpracována pouze tím klíčovým serverem, kterému je určena. Ostatní servery na cestě ji jen přeposílají dále.
Pro každé dva sousední servery v síti je známa doba potřebná k přenosu zprávy mezi těmito dvěma servery. Doba shromažďování statistik je doba, která uplyne od vyslání zprávy z prvního klíčového serveru až do okamžiku, kdy tento server opět obdrží zprávu s připojenými statistikami všech klíčových serverů. Doba shromažďování statistik může být různá podle toho, v jakém pořadí si jednotlivé klíčové servery postupně posílají zprávu se statistikami. Do doby shromažďování statistik se nezapočítáva doba, po kterou server zprávu zpracovává.

     

Obrázek 1. Schémata propojení sítě a), b), c) odpovídající příkladům 1, 2, 3, níže. Klíčové servery jsou znázorněny jako uzly s tmavým pozadím. Doby přenosu zprávy mezi sousedními servery jsou uvedeny u jednotlivých hran znázorňujících propojení sousedních serverů. Minimální doba shromažďování statistik je 34, 54, 62 v případě a), b), c). V případě a) může zpráva cestovat mezi klíčovými servery např. v pořadí 2 - 12 - 4 - 15 - 8 - 2. V případě b) může zpráva cestovat mezi klíčovými servery např. v pořadí 0 - 6 - 1 - 5 - 2 - 4 - 0. V případě c) může zpráva cestovat mezi klíčovými servery např. v pořadí 0 - 5 - 7 - 3 - 0. Pokud jsou klíčové servery alespoň tři, existuje vždy více různých pořadí klíčových serverů, v nichž zpráva cestuje a přitom trvá nejkratší možnou dobu.

Úloha

Je dána topologie sítě, seznam klíčových serverů a časy přenosu zprávy mezi každými dvěma sousedními servery. Určete minimální možnou dobu shromažďování statistik.

Vstup

První řádek obsahuje dvě celá čísla N, K oddělená mezerou a představující (v tomto pořadí) počet serverů v síti a počet klíčových serverů v síti. Servery v síti označeny čísly 0, 1, ..., N − 1. Na druhém řádku je v libovolném pořadí uveden seznam čísel klíčových serverů, čísla jsou oddělena mezerou. Následuje N − 1 řádků, každý specifikuje jednu dvojici sousedních serverů v síti. Řádek obsahuje tři celá čísla A, B, D oddělená mezerou. A a B jsou čísla sousedních serverů, D je doba přenosu zprávy mezi těmito dvěma servery. Doba D je stejná pro oba směry přenosu.
Platí: 2 ≤ N ≤ 106, 2 ≤ K ≤ 105, K ≤ N. Všechny doby přenosů zprávy mezi sousedními servery jsou kladné a menší než 103.

Výstup

Výstup obsahuje jeden textový řádek s jedním celým číslem udávajícím minimální možnou dobu shromažďování statistik.

Příklad 1

Vstup
16 5
2 12 4 8 15
2 3 3
4 5 5
7 8 3
10 11 4
11 12 1
13 14 2
14 15 3
6 11 4
0 3 1
3 7 1
7 12 1
1 4 2
4 8 2
8 13 2
9 14 3
Výstup
34
Schéma sítě v Příkladu 1 je znázorněno na Obrázku 1a).

Příklad 2

Vstup
7 6
6 5 4 2 1 0
0 3 5
1 3 6
2 3 6
4 3 5
5 3 2
6 3 3
Výstup
54
Schéma sítě v Příkladu 2 je znázorněno na Obrázku 1b).

Příklad 3

Vstup
9 4
0 3 5 7
0 1 8
1 2 7
0 3 6
3 4 5
4 5 8
5 8 7
6 7 6
7 8 5
Výstup
62
Schéma sítě v Příkladu 3 je znázorněno na Obrázku 1c).

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.
Veřejná data