Mentők

Adva van egy város, amelyben több mentőállomás és kórház működik. Riasztás esetén a diszpécser értesíti a riasztás helyszínéhez legközelebb eső mentőállomást, megad egy lehetséges legrövidebb útvonalat az állomástól a helyszínig, és megad egy legrövidebb útvonalat a helyszíntől a legközelebbi kórházig. Írjunk programot, amely meghatározza ezeket a legrövidebb útvonalakat!

Bemenet:

Adva van a város térképe. A térképen az útkereszteződések, a mentőállomások és a kórházak egy-egy nem negatív egész számmal vannak azonosítva, ezek egyike sem nagyobb 999-nél. Az útszakaszokat egy számhármas adja meg. A számhármas első két tagja egy-egy "szomszédos" útkereszteződés, mentőállomás vagy kórház azonosítója, a harmadik tag az útszakasz méterben megadott hossza. Egy útszakaszon a mentőautó mindkét irányba közlekedhet.

Az INPUT.TXT állomány első sorában szerepelő N egész szám (0<N<100000) megadja a térképen szereplő útszakaszok számát. A következő N sor tartalmazza a már említett útszakaszok leírására szolgáló számhármasokat.

Ezt követi egy egész szám (0<m<100), amely megadja a mentőállomások számát. A következő m egész szám a mentőállomások azonosítóit tartalmazzák. Ezt követi egy egész szám (0<k<100), amely megadja a kórházak számát. A következő k egész szám a kórházak azonosítóit tartalmazzák. Eddig a város topológiájának adatait adtuk meg. Ezután következnek a kérések. Minden kérés a riasztáshoz legközelebbi útkereszteződés azonosítóját tartalmazza. Az input végét egy -1-es szám jelzi.

Feltételezhetjük, hogy a mentőállomásokon mindig van szabad mentőautó, és az input állományban megadott kórházak, korlátlan mennyiségű beteget fogadhatnak.

Kimenet:

Minden kérésre adjuk meg a legrövidebb útvonal hosszát, majd az egyik legrövidebb útvonalat a mentőállomás és a riasztáshoz legközelebbi útkereszteződés ill. a kórház között, a mentőállomás, az útkereszteződések és a kórház azonosítójának vesszővel elválasztott felsorolásával. Amennyiben egyetlen mentőállomásról sem érhető el a riasztás helyszíne ill. egyetlen kórház sem elérhető a riasztás helyszínéről, írjuk ki, hogy "Helikopteres intezkedes szukseges!". Az egyes válaszok között hagyjunk ki egy üres sort.

Példa:

INPUT

OUTPUT

1 2 1

2 3 1

3 4 1

4 1 1

1 1

1 2

-1

2 : (1,2,3)

1 : (3,2)