Minimum Journey Cost with Magic Spells

C Country consists of \(n\) cities and \(m\) directed roads. Both cities and roads are numbered starting from 1. The cost to traverse the \(i\)-th road is \(t_i\).

You start from city 1 and your goal is to reach city \(n\). Additionally, you are allowed to cast magic at most \(k\) times. Each time you cast a magic, the cost to traverse the next road becomes its negation, i.e., the cost changes from \(t_i\) to \(-t_i\). Note that using the magic only affects the cost of that one traversal and does not permanently change the road's cost \(t_i\). A city, including city \(n\), may be visited multiple times. The final total cost may be negative.

Determine the minimum total cost needed to complete the journey from city 1 to city \(n\) while using the magic at most \(k\) times.

Input Constraints:

• The first line contains three integers \(n\), \(m\), and \(k\) indicating the number of cities, roads, and maximum spells respectively.
• The next \(m\) lines each contain three integers \(u\), \(v\), \(t\) representing a directed road from city \(u\) to city \(v\) with a travel cost of \(t\).

Note: The cost may be negative.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(k\). Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(t\), describing a directed edge from city \(u\) to city \(v\) with cost \(t\).

outputFormat

Output a single integer representing the minimum total cost required to travel from city 1 to city \(n\) using at most \(k\) magic spells.

sample

3 3 1
1 2 5
2 3 5
1 3 15

-15