Shortest Valid Route

You are given a directed graph representing a network of cities and one‐way roads. There are (n) cities numbered from 1 to (n). You are also given (m) roads. Each road is described by three integers (u), (v), and (w), where (u) is the starting city, (v) is the destination city, and (w) is the length of the road. However, if (w = -1), that road is under construction and cannot be used. Your task is to find the shortest route from city 1 to city (n) using only roads that are not under construction. If no such route exists, output "NO".

Note: You can assume that all roads with (w \neq -1) have non-negative weights.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (n) and (m) separated by a space, representing the number of cities and the number of roads, respectively. The following (m) lines each contain three integers (u), (v), and (w) separated by spaces, where (u) and (v) denote the start and end cities of a road and (w) is its length. If (w) equals -1, that road is under construction and cannot be used.

outputFormat

Output the length of the shortest route from city 1 to city (n) to standard output (stdout). If there is no such route, output "NO".## sample

5 6
1 2 3
2 3 -1
2 4 2
3 5 4
4 5 3
1 3 10

8