Dadlı Qəlyanaltı#10399

Dadlı Qəlyanaltı

2 saniyə

128 meqabayt

Çətin

İnəklər uzun bir günün sonunda, həm yorğun, həm də ac vəziyyətdə tövləyə qayıdırlar.

Ferma $n$ otlaqdan ibarətdir və onlar $1$ -dən $n$ -ə qədər nömrələnmişdir. Bütün inəklər $n$ nömrəli otlaqda yerləşən tövləyə çatmaq istəyirlər. Digər $n - 1$ n - 1 otlaqdan hər birində bir inək yerləşir. İnəklər $m$ ədəd yönəlməmiş cığır vasitəsilə otlaqlar arasında hərəkət edə bilərlər. $i$ -ci cığır $a_{i}$ a_i və $b_{i}$ b_i otlaqlarını birləşdirir və keçmək üçün $t_{i}$ t_i vaxt tələb edir. Hər bir inək hansısa cığır ardıcıllığı ilə tövləyə çata bilər.

Ac olduqları üçün inəklər evə gedərkən qəlyanaltı etmək üçün dayanmaq istəyirlər. Əlverişli şəkildə, $k$ otlaqda ləzzətli ot tayaları var və $i$ -ci ot tayasının ləzzətlilik dəyəri $y_{i}$ y_i-dir. Hər bir inək tövləyə gedən yolunda bir ot tayasında dayanmağa hazırdır, lakin yalnız bu, onun tövləyə ən qısa yoluna nisbətən səyahət vaxtını ən çox ziyarət etdiyi ot tayasının ləzzətliliyi qədər artırırsa. Qeyd edək ki, inək "rəsmi olaraq" yemək üçün ən çox bir ot tayasını ziyarət edir; onun marşrutunun başqa ot tayaları olan otlaqlardan keçməsinin fərqi yoxdur — o sadəcə onları nəzərə almır.

Hər bir inək üçün, onun tövləyə gedən yolunda hansısa ot tayasında dayana bilib-bilmədiyini müəyyən edin.

Giriş

Birinci sətirdə üç tam ədəd verilir: $n$ , $m$ və $k (2 \leq n \leq 5 \cdot 1 0^{4}, 1 \leq m \leq 1 0^{5}, 1 \leq k \leq n)$ k~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 10^5, 1 \le k \le n). Növbəti $m$ sətirdən hər biri üç tam ədəd olan $a_{i}$ a_i, $b_{i}$ b_i və $t_{i} (a_{i} \neq = b_{i}, 1 \leq t_{i} \leq 1 0^{4})$ t_i~(a_i \ne b_i, 1 \le t_i \le 10^4) ehtiva edir və bu, $a_{i}$ a_i və $b_{i}$ b_i otlaqları arasında keçmək üçün $t_{i}$ t_i vaxt tələb edən cığırı təsvir edir.

Növbəti $k$ sətirdən hər biri bir ot tayasını təsvir edir və iki tam ədəd ehtiva edir: ot tayasının yerləşdiyi otlağın nömrəsi və onun ləzzətlilik dəyəri $y_{i} (1 \leq y_{i} \leq 1 0^{9})$ y_i~(1 \le y_i \le 10^9). Bir neçə ot tayası eyni otlaqda yerləşə bilər.

Çıxış

$n - 1$ n - 1 sətir çap edin. $i$ -ci sətirdə, əgər $i$ otlağındakı inək tövləyə gedən yolunda hansısa ot tayasında dayanıb qəlyanaltı edə bilirsə $1$ , əks halda $0$ çap edin.

Nümunələr

Nümunə 1

Qeyd

Bu misalda, $3$ nömrəli otlaqdakı inək qəlyanaltı üçün dayanmalıdır, çünki onun səyahət vaxtı yalnız $6$ vahid artır (2-dən 8-ə), bu isə ot tayasının ləzzətliliyi olan $7$ -dən çox deyil. $2$ nömrəli otlaqdakı inək, şübhəsiz ki, $2$ nömrəli otlaqdakı otu yeməlidir, çünki bu onun optimal marşrutunu heç dəyişdirmir. $1$ nömrəli otlaqdakı inək isə maraqlı bir haldır: ilk baxışdan onun optimal marşrutunun (uzunluğu $10$ ) dayanmaq üçün həddindən artıq uzanacağı düşünülə bilər. Lakin onun elə bir marşrutu var ki, orada dayanmaq əvəzinə dəyər: $4$ nömrəli otlağa get, sonra $2$ nömrəli otlağa get (orada otu ye), və sonra geri $4$ nömrəli otlağa qayıt.