zmeu

Zmeul le-a inchis pe cele 5 fete ale imparatului in castelul sau. Fat-Frumos a venit sa le scoata din castel, folosind harta pe care i-a dat-o zana buna. Pe harta sunt desenate cele n camere ale castelului, numerotate de la 1 la n si cele m tuneluri dintre camere. De asemenea sunt marcate camerele in care se gasesc fetele si Fat-Frumos, timpul necesar traversarii fiecarui tunel si cele p camere din care se poate iesi din castel.

Cerinta

Determinati timpul minim necesar lui Fat-Frumos pentru a lua cele 5 fete si a le scoate din castel.

Date de intrare

Pe prima linie a fisierului de intrare zmeu.in sunt scrise numerele n, m si p, reprezentand numarul de camere, numarul de tunele si respectiv numarul de iesiri din castel.
Pe a doua linie sunt scrise numerele a 6 camere distincte: primul numar e camera in care se afla Fat-Frumos, iar celelalte 5 sunt camerele fetelor.
Pe urmatoarele m linii sunt cate 3 numere, reprezentand cele m tunele: primele doua reprezinta camerele intre care face legatura tunelul, al treilea timpul necesar traversarii tunelului.
Ultimele p linii contin cate un numar reprezentand camerele din care se poate iesi din castel. Toate numerele sunt intregi strict pozitive, iar numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de iesire

Prima linie a fisierului zmeu.out va contine un singur numar, timpul minim necesar pentru a porni din camera lui Fat-Frumos, a trece prin camerele celor 5 fete si a ajunge intr-o camera care are iesire in afara. Se va lua in considerare numai timpul traversarii tunelurilor, neglijandu-se timpul traversarii camerelor sau a iesirii din castel. 

Restrictii

Exemplu

zmeu.in

zmeu.out

 Explicatie

10 11 3
2 1 7 5 10 6
1 7 3
1 2 2
1 3 4
2 3 2
2 8 1
2 4 3
3 4 2
3 5 2
3 6 5
6 10 3
6 9 4
7
4
8

29

 Un traseu posibil este:
2-1-7-1-2-3-5-3-6-10-6-3-4

Timp maxim de executie/test: 1 secunda

prof. Nistor Mot
Colegiul National "N.Balcescu" Braila
Contact:emotz_ro@yahoo.co.uk