I. Ровно k перелётов до каждого

Как классная задача I, но ответ выводится для каждого города.

Разница с предыдущей задачей — ровно та же, что между классными H и I: новый слой начинается с бесконечностей, а не с копии предыдущего.

Обратите внимание, что даже город вылета может оказаться недостижим за ровно $k$ перелётов: вернуться в него можно только по циклу подходящей длины.

Первая строка содержит числа $n$ ($2 \le n \le 100$), $m$ ($1 \le m \le 10^5$), $k$ ($1 \le k \le 100$) и $s$.

Далее идут $m$ строк: город вылета, город прилёта и стоимость $p$ ($1 \le p \le 10^6$).

Одна строка из $n$ чисел.