Safest Path

You are given a directed graph that represents a series of rooms and one‐way passageways. The graph has (n) rooms numbered from (0) to (n-1). Each passageway from room (u) to room (v) has an associated danger level (a positive integer). Your task is to compute the minimum total danger (i.e. the sum of danger levels) along any path from the starting room (room 0) to the target room (room (n-1)). If no such path exists, output (-1).

Input is provided from standard input. The first line contains two integers (n) and (m), representing the number of rooms and the number of directed edges respectively. Each of the following (m) lines contains three integers (u), (v), and (d) indicating that there is a passage from room (u) to room (v) with danger level (d).

inputFormat

The first line contains two integers (n) and (m) (the number of rooms and edges respectively). Each of the next (m) lines contains three integers (u), (v), and (d), meaning there is a directed edge from room (u) to room (v) with danger level (d).

outputFormat

Output a single integer representing the minimum total danger from room 0 to room (n-1). If there is no valid path, print (-1).## sample

4 4
0 1 1
0 2 4
1 3 1
2 3 2

2