Zərif mətbəx
İnəklər uzun bir günün sonunda tövləyə qayıdırlar və özlərini yorğun və ac hiss edirlər.
Fermada n otlaq var, ardıcıl olaraq 1..n nömrələnmişdir. İnəklər n otlağındakı tövləyə çatmaq istəyirlər. Qalan n − 1 otlağın hər birində dəqiq 1 inək var. İnəklər m yönsüz yollar dəstəsi ilə otlaqdan otlağa hərəkət edə bilərlər. i-ci yol a[i] və b[i] otlaqlarını birləşdirir və onu keçmək üçün t[i] vaxt tələb olunur. Hər bir inək tövləyə çatmaq üçün müəyyən bir yol ardıcıllığını keçə bilər.
Aclar, inəklər evə gedərkən yemək üçün dayanacaqlarla maraqlanırlar. Xoşbəxtlikdən, k otlaqda ot tayaları var, bu tayaların i-ci dadlılıq dəyəri y[i]dir. Hər biri tövləyə gedərkən bir belə ot tayasını yemək istəyir, amma yalnız əlavə olunacaq vaxt, yediyi tayanın dadlılıq dəyərindən çox deyilsə. Qeyd edək ki, inək bir ot tayasından çoxunu yeyə bilməz. Əgər yolunda başqa ot tayaları olan otlaqlar varsa, onları sadəcə görməzlikdən gəlir.
Giriş Məlumatları
Birinci sətir üç boşluqla ayrılmış tam ədəd n (2 ≤ n ≤ 50000), m (1 ≤ m ≤ 10^5), k (1 ≤ k ≤ n) ehtiva edir. Sonrakı m sətirin hər biri üç tam ədəd a[i], b[i], t[i] ehtiva edir, a[i] və b[i] otlaqları arasında olan yolu təsvir edir və onu keçmək üçün t[i] vaxt tələb olunur (a[i] və b[i] bir-birindən fərqlidir və t[i] müsbət tam ədəd 10^4-dən çox deyil).
Sonrakı k sətirin hər biri ot tayasını iki tam ədəd ilə təsvir edir: otlağın indeksi və tayanın dadlılıq dəyəri (müsbət tam ədəd 10^9-dan çox deyil). Ot tayalarının dəsti eyni otlaqda yerləşə bilər.
Çıxış Məlumatları
Çıxış n − 1 sətir ehtiva etməlidir. i-ci sətir bir tam ədəd 1 ehtiva edir, əgər i otlağındakı inək ot tayası olan otlağı ziyarət edə və bu tayadan yeyə bilirsə və 0 əks halda.
Nümunə
Bu nümunədə 3 otlağındakı inək yemək üçün dayanmalıdır, çünki onun marşrutu yalnız 6 ( 2-dən 8-ə) artacaq və o, dadlılığı 7 olan tayadan yeyəcək (6 <= 7). 2 otlağındakı inək 2 otlağında tayadan yeməlidir. 1 otlağındakı inək maraqlı bir haldır, çünki o, optimal marşrutunu (uzunluğu 10) keçə bilər, lakin əslində onun yeməkli bir marşrutu var - əvvəlcə 4 otlağına, sonra 2 otlağına (tayadan yemək), sonra yenidən 4 otlağına.