Sindra is stuck in Italy! While this would not commonly be a problem, they are in danger, for Sindra greatly enjoys the consumption of pineapple on pizza.

Italy can be represented as a graph of ~n~ nodes and ~m~ edges. Each edge has a weight ~w[i]~, representing how many angry italians will verbally abuse Sindra if they choose to cross that street.

As Sindra's FIT2004 lecturer, can you help them discover the minimum number of times they could be verbally abused as they traverse the graph from node ~0~ to node ~n-1~?

Input Format

The first line of input will consist of two integers, ~n~ and ~m~. The following ~m~ lines will each consist of three integers ~a~ ~b~ ~c~, representing the starting position, ending position and cost respectively of a single edge.

Output Format

The output should consist of a single integer, the minimum number of verbal abuses.

Constraints

~1 \le n \le m \le 1e5~

~0 \le a,b \le n-1 ~

~1 \le c \le 1e3~

Sample Input

3 3
0 2 11
0 1 5
1 2 5

Sample Output

10

Sample Explanation

The optimal route is ~0->1->2~, resulting in ~5+5=10~ cost. This is the minimum number.