Laiko ribojimas: 2s

Atminties ribojimas: 16MB

Duomenų failas: autobusas.in

Rezultatų failas: autobusas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Mokyklinis autobusas

Kaip manote, ar Amerikoj tikrai vaikus į mokyklą vežioja tokie geltoni ir faini autobusai, kokius mes matom filmuose?.. Na, jei vežioja, tai turbūt juos vairuoja apkūnūs dėdės, mėgstantys ilgai pamiegoti. Matyt, jie kiekvieną rytą galvoja:

autobusas

Ak, kodėl aš turiu keltis taip anksti?.. Tik tam, kad surankiočiau visus tuos vaikus iš velniai žino kur... O jų tiek daug. Kažin, gal galėčiau kaip nors sutaupyti laiko, jei važiuočiau trumpesniu maršrutu? Bent penkiolika minučių saldaus miego...

Tuomet vairuotojai keliasi, pėdina iki mokyklų, sėda į autobusus, apvažiuoja visas sankryžas, kuriose laukia vaikai, ir nuveža juos į mokyklą.

Kiekvienas maršrutas prasideda ir baigiasi sankryžoje prie mokyklos. O be to, kad moksleiviai neįprastų vėluoti į autobusą, pro kiekvieną sankryžą pravažiuojama lygiai vieną kartą.

Parašykite programą, kuri, žinodama atstumus tarp sankryžų bei dabartinį vairuotojo maršrutą, rastų, kiek daugiausiai miego galima sutaupyti, važiuojant geresniu maršrutu.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašyti du sveikieji skaičiai N ir M (1\\leN\\le15). N yra sankryžų, kuriose vaikai laukia autobuso, skaičius. Sankryžos sunumeruotos nuo 1 iki N; sankryžoje nr. 1 yra prie mokyklos (joje vairuotojas pradeda savo rytinę kelionę). M - yra rajono gatvių skaičius.

Sekančiose M eilučių surašyti sveikų skaičių trejetai a_i, b_i ir d_i: (a_i, b_i) žymi sankryžų porą, kurią jungia di metrų ilgio gatvė (d_i <= 5000). Kiekvieną sankryžų porą jungia ne daugiau negu viena gatvė.

Paskutinėje eilutėje įrašyta N + 1 skaičių seka - tai dabartinis vairuotojo maršrutas: skaičiai nurodo, kuria tvarka apvažiuojamos sankryžos. Ši seka yra korektiška: lygiai vieną kartą aplankomos visos sankryžos, pradedama ir baigiama pirmojoje sankryžoje.

Rezultatai

Jei dabartinis vairuotojo maršrutas yra optimalus, į pirmą rezultatų failo eilutę programa turi įrašyti sakinį Ilgiau pamiegoti nepavyks..

Priešingu atveju, į pirmą eilutę programa turi įrašyti sakinį Galima pamiegoti dar m min., kur m - minučių skaičius, kurį vairuotojas sutaupytų, jei važiuotų optimaliu maršrutu (vienam kilometrui nuvažiuoti vidutiniškai sugaištamos 5 minutės, programa atsakymą turi suapvalinti iki minučių tikslumo).

Pavyzdžiai

Pradiniai duomenys Rezultatai 
6 10
1 3 1000
1 4 2500
1 6 1500
2 3 1500
2 4 1000
2 5 5000
3 5 2000
3 6 1000
4 5 500
5 6 1500
1 6 5 3 2 4 1
 
Galima pamiegoti dar 15 min.
 
6 10
1 3 1000
1 4 2500
1 6 1500
2 3 1500
2 4 1000
2 5 5000
3 5 2000
3 6 1000
4 5 500
5 6 1500
1 6 5 4 2 3 1
 
Ilgiau pamiegoti nepavyks.