Un cop per setmana el director de l'ITB fa la ronda per totes les aules. Ell diu que "només passava a saludar i desitjar un bon dia", però tothom sap que entre aula i aula treu el tablet que porta amagat i apunta tot el que ha vist: tant si és bo com si és dolent.

L'edifici de l'ITB és un edifici reformat de vàries plantes. Abans era una escola de primària i, el que poca gent coneix, és que hi han passadissos secrets entre algunes aules. També tenim un projecte de portes de teletransportació per tal que puguis anar entre dues aules sense cap esforç i ja existeixen algunes portes instal·lades a l'edifici. A més a més, contínuament hi ha obres a l'edifici i, alguna vegada, els alumnes s'han trobat que no poden arribar i/o sortir de l'aula.

El director ja té estudiat el recorregut òptim per visitar les aules mentre va apuntant amb la tablet tot el que veu, però aquesta setmana el seu tablet ha fet figa i l'ha enviat a reparar, així que entre una visita d'aula i una altra haurà de tornar al seu despatx per registrar tot el que ha vist al seu ordinador. Com que és un edifici molt gran, vol calcular la forma de fer la ronda amb el mínim esforç possible.

Pots ajudar al director a calcular l'esforç mínim necessari per fer la ronda setmanal?

Entrada

L'entrada comença amb un número N d'aules que cal visitar (entre 1 i 1.000). La segona línia té un altre número C de conexions directes entre aules (entre 1 y 10.000). A continuació tenim C línies cadascuna amb tres enters que indiquen l'aula d'origen, l'aula de destí i l'esforç d'anar des de l'origen fins al destí. Les aules estan numerades des de l' 1 fins a N i l'esforç pot anar entre 0 i 10.000. Si el camí és bidireccional el tindrem dues vegades, ja que l'edifici té vàries plantes i no costa el mateix pujar que baixar.

Un cop feta la descripció del centre, tenim una línia amb dos números enters: D és el número d'aula on es troba el despatx del director (el recorregut que ha de fer el director comença al seu despatx i ha d'acabar també al seu despatx), i A (valor entre 1 i N) és el número d'aules que cal visitar (no cal visitar totes les aules, sinó només aquelles en les que es fa classe). A continuació, hi ha una altra línia amb les A números de les aules que cal visitar.

Sortida

Per a cada cas de prova el programa ha d'escriure una línia amb l'esforç mínim que cal per visitar les aules indicades. En el cas que degut a les obres no sigui possible visitar totes les aules, el programa escriurà "NOT POSSIBLE"

Exemple d'Entrada

4
3
1 2 3
2 1 4
4 3 2
1 2
2 3
6
6
1 2 0
2 3 1
3 4 5
4 1 3
1 4 1
5 6 9
4 3
1 2 3

Exemple de Sortida

NOT POSSIBLE
22