Problem Description

Country C consists of $n$ cities and $m$ directed roads. Both cities and roads are numbered starting from $1$. Traversing road $i$ costs $t_i$.

Now you want to travel from city $1$ to city $n$. You may cast magic at most $k$ times, so that when you traverse the next road, the cost becomes the opposite of the original, i.e. the cost changes from $t_i$ to $-t_i$. Please compute the minimum total cost needed to finish this trip.

Note: Casting magic only changes the cost for one traversal, and does not change the road’s own $t_i$. The final total cost may be negative, and a city may be visited multiple times (including city $n$).

Input Format

The first line contains three integers, representing the number of cities $n$, the number of roads $m$, and the limit on the number of times you can cast magic $k$.

Lines $2$ to $(m + 1)$ each contain three integers. On line $(i + 1)$, the integers $u_i, v_i, t_i$ indicate that there is a one-way road from $u_i$ to $v_i$, and traversing it costs $t_i$.

Output Format

Output one integer in one line, representing the minimum total cost.

4 3 2
1 2 5
2 3 4
3 4 1

-8

2 2 2
1 2 10
2 1 1

-19

Hint

Explanation for Sample Input/Output 1

Traverse road $1$, road $2$, and road $3$ in order, and cast magic before traversing roads $1$ and $2$.

Explanation for Sample Input/Output 2

Traverse road $1$, road $2$, and road $1$ in order, and cast magic before both times you traverse road $1$.

Constraints

This problem has $20$ test points. The information for each test point is shown in the table below.

For test points where the “Acyclic” column is “Yes”, it is guaranteed that the given graph is a directed acyclic graph; otherwise, there is no guarantee about the graph structure.

For all test points, it is guaranteed that:

• $1 \leq n \leq 100$, $1 \leq m \leq 2500$, $0 \leq k \leq 10^6$.
• $1 \leq u_i, v_i \leq n$, $1 \leq t_i \leq 10^9$.
• The given graph has no multiple edges or self-loops, and there exists at least one path from $1$ to $n$.

**Unofficial testdata is generated within 5 minutes using CYaRon. If you find any issues with the testdata, please post in the discussion board or send a private message to

Translated by ChatGPT 5