H. Стоимость до каждого города

Как классная задача H, но выведите наименьшую стоимость пути не более чем за $k$ перелётов до каждого города.

Массив слоёв и так считается для всех городов сразу — меняется только вывод. Для города вылета ответ равен нулю, для недостижимых за $k$ перелётов — $-1$.

Первая строка содержит числа $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$ чисел.