Pink Floyd#2966
Pink Floyd qrupu dünya üzrə yeni konsert turuna çıxır. Əvvəlki təcrübəyə əsaslanaraq, qrup bilir ki, baş müğənni Roger Waters uçuş zamanı daim həyəcan keçirir. Bəzi marşrutlarda o, həyəcanından çəkisini itirir, digərlərində isə çox yeyir və çəkisini artırır.
Məlumdur ki, Roger nə qədər ağırdırsa, qrup bir o qədər yaxşı çıxış edir. Ona görə də marşrutlar elə planlaşdırılmalıdır ki, Roger-in çəkisi hər konsertdə mümkün qədər yüksək olsun.
Qrup konsert verdiyi şəhərləri eyni ardıcıllıqla ziyarət etməlidir və konsertlər arasında aralıq şəhərlərə də baş çəkə bilər.
Giriş faylının birinci sətrində üç natural ədəd , və — dünyadakı şəhərlərin sayı, uçuşların sayı və qrupun verməli olduğu konsertlərin sayı verilir (n \leq 100,\ m \leq 10000,\ 2 \leq k \leq 10000). Şəhərlər -dən -ə qədər nömrələnmişdir.
Sonrakı sətrin hər birində uçuşlar təsvir edilir. -ci uçuş üç ədəd ilə verilir: b_i, e_i və w_i — uçuşun başlandığı və bitdiyi şəhərin nömrəsi, Roger-in çəkisində gözlənilən dəyişmə (milliqramla) (1 \leq b_i,\ e_i \leq n,\ -100000 \leq w_i \leq 100000).
Sonuncu sətirdə a_1, a_2, \ldots, a_k ədədləri — konsertlərin keçirildiyi şəhərlərin nömrələri verilir (a_i \neq a_{i+1}). Konsert turunun əvvəlində qrup a_1 şəhərindədir.
Zəmanət verilir ki, qrup bütün konsertləri keçirə bilər.
Çıxış faylının birinci sətrində — qrupun etməli olduğu uçuşların sayı verilməlidir. İkinci sətrdə isə ədəd — istifadə olunan uçuşların nömrələri göstərilməlidir.
Əgər elə uçuşlar ardıcıllığı varsa ki, bu zaman Roger sonsuz çəki yığa bilər, o zaman çıxışın birinci sətrində infinitely kind mesajı verilməlidir.
Nümunə 1