Benny appeared in a Magic labyrinth. Labyrinth consists of rooms and doors. Doors are unidirectional, they can be used only in one direction. There are even doors from the room to itself. When passing through the door, the master of the labyrinth gives Benny a coin.
Benny can move through the doors as much as she wants. But the only goal of the game is to get the score as high as possible. If Benny doesn't use any door, her score is 0. Let the maximum value of coin earned by Benny is p and minimum value of coin earned by Benny is q, then the score is p−q. Help Benny to learn, what is the maximum score she can achieve.
Input format
First line contains two integers n and m — number of rooms in Magic labyrinth and number of doors.
Next m lines contain description of doors. Each line contains three integers v, u and w, describing a door that can be used to go from room v to room u getting coin of value w.
Constraints
2≤n≤3⋅105
1≤m≤3⋅105
1≤v,u≤n
0≤w≤109
Output format
Output single integer: maximum score which Benny can achieve.
One of the optimal paths is: 2→3→1→2→4→5→6→4. Which gives score equal to 10−1=9.
