Description

Alice and Bob are going to travel by plane, and they chose a relatively cheap airline. This airline operates in $n$ cities, labeled $0$ to $n-1$, and there are $m$ routes. Each route connects two cities and has a certain price.

Alice and Bob need to travel from one city to another along these routes, and they may transfer. The airline offers a discount for this trip: they can take flights on at most $k$ routes for free. What is the minimum total cost for their trip?

Input Format

The first line contains three integers $n, m, k$, representing the number of cities, the number of routes, and the maximum number of free rides, respectively.

The next line contains two integers $s, t$, representing the starting city and the destination city.

The next $m$ lines each contain three integers $a, b, c$, indicating that there is a bidirectional route between cities $a$ and $b$ with price $c$.

Output Format

Output a single integer on one line, which is the minimum total cost.

5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

8

Hint

Constraints

For $30\%$ of the testdata, $2 \le n \le 50$, $1 \le m \le 300$, $k=0$.

For $50\%$ of the testdata, $2 \le n \le 600$, $1 \le m \le 6\times10^3$, $0 \le k \le 1$.

For $100\%$ of the testdata, $2 \le n \le 10^4$, $1 \le m \le 5\times 10^4$, $0 \le k \le 10$, $0 \le s,t,a,b < n$, $a \ne b$, $0 \le c \le 10^3$.

There is also a set of hack testdata.

Translated by ChatGPT 5