Coolest Ski Route

John loves winter. Every skiing season he goes heli-skiing with his friends. To do so, they rent a helicopter that flies them directly to any mountain in the Alps. From there they follow the picturesque slopes through the untouched snow.

Of course they want to ski on only the best snow, in the best weather they can get. For this they use a combined condition measure and for any given day, they rate all the available slopes.

Can you help them find the most awesome route?

Input

The first line contains two integers $n(2\le n\le 1000)$ and $m(1\le m\le 5000)$, where $n$ is the number of ($1$-indexed) connecting points between slopes and $m$ is the number of slopes.

Each of the next $m$ lines contains three integers $s,t,c(1\le s,t\le n,1\le c\le 100)$ representing a slope from point $s$ to point $t$ with condition measure $c$.

Points without incoming slopes are mountain tops with beautiful scenery, points without outgoing slopes are valleys. The helicopter can land on every connecting point, so the friends can start and end their tour at any point they want. All slopes go downhill, so regardless of where they start, they cannot reach the same point again after taking any of the slopes.

Output

Output a single number — the maximum sum of condition measures along a path that the friends could take.

Examples