Egy országban N város van. Az egyik városban futárok várakoznak. Ismerjük azt is, hogy az egyes városokból mennyi idő alatt lehet elérni valamilyen járművel adott másik városokat. (Feltételezzük, hogy a futárok városából / "telephelyéről" az összes többi település elérhető megfelelő járművekkel.) 

Írjunk programot, ami megadja, hogy minimum mennyi idő alatt jutnak el a futárok az összes városba.

A bemenet első sora három számot tartalmaz:

• 1 <= N <= 100: a városok száma
• 1 <= M <= 5000: a járművek száma
• 1 <= H <= N: a futárok kezdő helye

Ezután M sorban a járművek leírása következik: az indulás és az érkezés városának sorszáma, majd az út megtételéhez szükséges idő (1 <= T <= 1000).

A kimenet állományba egyetlen sort kell írni, a minimális időt, ami alatt a futárok az összes városba elérnek.

Bemenet	Kimenet
6 12 1 1 6 20 1 5 10 5 6 5 6 2 10 1 2 15 2 3 10 3 4 10 3 5 10 1 6 25 3 5 5 6 1 20 6 5 5	35

Magyarázat

futar.zip

A feladat forrása: NTOITV, 2010, 11-13. évfolyam, 2. forduló, 3. feladat

Algoritmusok: egy pontból kiinduló legrövidebb utak, Dijkstra-algoritmus