Detour Route in Beaverland

In Beaverland, there are $N$ cities numbered from $1$ to $N$, and $M$ bidirectional roads. The $i$-th road connects cities $A_i$ and $B_i$ and has length $C_i$. It is guaranteed that any city is reachable from any other city by some sequence of roads.

Bitaro, a beaver living in city $1$, goes to school in city $N$ every day using one of the shortest paths (with distance $L$, the minimum distance from city $1$ to city $N$). Today, enjoying the fine weather, he decides to take a detour on his way back home. That is, he wants to choose a route from school (city $N$) to his home (city $1$) whose total length is (> L). While taking the detour, he does not wish to pass any city more than once and he is not allowed to traverse the same road back and forth (i.e. no immediate backtracking). Note that although he is not allowed to visit the same city twice on the detour route, passing through a city which appeared on his school route is allowed.

Your task is to determine whether there exists such a detour route from city $N$ to city $1$ that meets the conditions.

inputFormat

The input begins with two integers $N$ and $M$ ($2 \le N \le 10^5$, $1 \le M \le 2\times10^5$) on the first line, representing the number of cities and the number of roads respectively. The next $M$ lines each contain three integers $A_i$, $B_i$, and $C_i$ ($1 \le A_i,B_i \le N$, $1 \le C_i \le 10^9$), describing a road between cities $A_i$ and $B_i$ with length $C_i$. It is guaranteed that the graph is connected.

outputFormat

Output a single line with the word “YES” if there exists a detour route from city $N$ to city $1$ with a length strictly greater than the shortest distance (L) from city $1$ to city $N$ (and without repeating any city). Otherwise, output “NO”.

sample

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

NO