Бесплатные билеты

В ориентированном графе разрешено сделать не более $k$ рёбер бесплатными. Найдите кратчайший путь из вершины 1 в вершину $n$.

В первой строке $n$, $m$ и $k$ ($2 \le n \le 10^5$, $0 \le m \le 2 \cdot 10^5$, $0 \le k \le 10$). В каждой из следующих $m$ строк — числа $a_i$, $b_i$, $w_i$ ($1 \le w_i \le 10^9$) — ориентированное ребро.

Выведите длину кратчайшего пути или $-1$, если пути нет.