Pink Floyd

Pink Floyd qrupu dünya üzrə yeni konsert turuna çıxdılar. Əvvəlki təcrübəyə əsasən qrup bilir ki, solist Rojer Uoters həmişə uçuş zamanı əsəbiləşir. Bəzi marşrutlarda o həyəcandan çəkisini itirir, digərlərində isə çox yeyir və çəkisini artırır.

Məlumdur ki, Rojerin çəkisi nə qədər çox olursa, qrup daha yaxşı çıxış edir, buna görə də uçuşları elə planlaşdırmaq lazımdır ki, hər bir konsertdə Rojerin çəkisi mümkün qədər ən çox olsun.

Qrup hər bir şəhərdə konsertləri verdiyi ardıcıllıqda olmalıdır, bu zaman konsertlər arasında qrup aralıq şəhərlərdə də ola bilər.

Giriş verilənləri

Giriş faylının ilk sətri dünyadakı şəhərlərin sayını, reyslərin sayını və qrupun verəcəyi konsertlərin sayını ifadə edən üç natural $n$, $m$ və $k$ $(n\le 100,m\le 10000,2\le k\le 10000)$ ədədlərini ehtiva edir. Şəhərlər $1$-dən $n$-ə qədər ədədlərlə nömrələnir.

Növbəti $m$ sətrin hər biri reyslərin təsvirini ehtiva edir. $i$ nömrəli reys reysin başlanğıc və son şəhərlərinin nömrələrini və Rojerin çəkisinin ehtimal olunan dəyişməsinin milliqramla qiymətini ifadə edən üç $b_i$, $e$_i və $w_i$ ədədləri ilə təsvir olunur $(1\le b_i,e_i\le n,-100000\le w_i\le 100000)$.

Sonuncu sətir konsertlərin keçiriləcəyi şəhərlərin $a_1$, $a_2$, ..., $a_k$ $(a_i\ne a_{i+1})$ nömrələrini ehtiva edir. Konsert turunun əvvəlində qrup $a_1$ şəhərində olur.

Qrupun bütün konsertləri verə biləcəyinə zəmanət verilir.

Çıxış verilənləri

Çıxış faylının ilk sətri qrupun edəcəyi reyslərin $l$ sayını ehtiva etməlidir. İkinci sətir istifadə edilən reyslərin nömrələrini ifadə edən $l$ sayda ədəd ehtiva etməlidir.

Əgər konsertlər arasında Rojerin məhdud olmayan çəki əldə etməsi üçün marşrutlar ardıcıllığı mövcud olarsa, onda giriş faylının ilk sətri 'infinitely kind' ismarışını ehtiva etməlidir.

Nümunələr