write python code

Super Mario

$58$m Coding

Problem Statement

Mario found a mysterious map that leads to treasure. There are $N$ places starting from $1,2,$dots,$N.$ The treasure is kept at the last destination place $N.$

There are a total of $M$ routes. Each route can take Mario from one place to another. The routes are unidirectional. Each route takes some time to complete.

Mario also knows a magic trick to complete a route in half the given time, but he can use this magic only once. Mario is your friend; he is asking for your help to find the minimum time to reach the last destination, $N,$ starting from the $1$st destination.

Note: Consider the integer part while calculating the Half time of the Original time.

Input Format

The first line contains an integer $N-$the last destination.

The second line contains an integer, $M,$ which stands for the Number of Routes.

The third line contains an integer $3-$ representing the column number.

In the next $M$ lines, each line contains $3$ integers $A,B,$ and $C$ representing that there is a route from $A$ to $B,$ and it takes $C$ time to complete that route.

Output Format

Output Format

Print the Minimum time to reach the treasure.

Constraints

$2N100000$

$1M200000$

$1A,BN$

$1C{10}^9$

Evaluation Parameters

Sample Input

$3$

$4$

$3$

$123$

$2,3,1$

$137$

$215$

Sample Output

$2$

Explanation

To reach the $3^{rd}$ destination in Minimum time, we can use the following routes

$12=1($we are using magic in this route$)).$