Benny and Some Magic
Tag(s):

Algorithms, DFS, Medium

Problem
Editorial
Analytics

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 \le n \le 3 \cdot 10^5$
$1 \le m \le 3 \cdot 10^5$
$1 \le v, u \le n$
$0 \le w \le 10^9$

Output format

Output single integer: maximum score which Benny can achieve.

SAMPLE INPUT
6 8
1 2 9
2 3 7
3 1 1
2 4 5
3 4 4
4 5 6
5 6 3
6 4 10

SAMPLE OUTPUT
9

Explanation

One of the optimal paths is: $2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 4$. Which gives score equal to $10 - 1 = 9$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...