H. Авиаперелёты

Профессор летает только ночными рейсами и за одну ночь совершает не больше одного перелёта. До конференции осталось $k$ ночей. Найдите наименьшую стоимость пути из города $s$ в город $f$, использующего не более $k$ рейсов.

Ограничение на число рёбер — это ровно то, что считает Форд — Беллман по фазам. После $j$-й фазы величина $d_j[v]$ — наименьшая стоимость пути не более чем из $j$ рёбер:

Ответ — $d_k[f]$.

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

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

Одно число — наименьшая стоимость или $-1$.