Bog of Eternal Stench

You are trying to reach the center of a Labyrinth, so you must cross the Bog of Eternal Stench. Legend says that if you put so much as one toe in the Bog, you will smell bad forever. You would of course prefer to cross the Bog with the lowest stench possible.

Luckily, you have determined earlier that the stench does eventually wear off, and that some areas of the Bog transfer more stench to you than others. There are also small islands where you can rest without any effect on your stench level. The first island is where your journey through the Bog starts, and the last is your destination on the other side.

From each island, established bridges let you travel to other islands, but each bridge works in one direction only. Because this is the Bog of Eternal Stench, most bridges increase your overall stench by a fixed amount. Some bridges are pleasant, though, and decrease your overall stench when you cross them. Your stench level can never drop below $0$: a bridge that would push it under $0$ sets it to $0$ instead.

You have mapped all islands and bridges and measured how much each bridge increases or decreases your stench. As a result, it may be possible to cross the Bog and come out with no stench at all!

Your top priority is reaching the destination island with the minimum stench. You are willing to take a circuitous path that visits some islands multiple times if that achieves this goal. Your path must end at the destination island, but you do not have to leave the Bog right away the first time you reach it, if a detour that returns to the island later would decrease your final stench value.

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 2\,000$), where $n$ is the number of islands and $m$ is the number of direct bridges.

Each of the next $m$ lines contains three integers $u$, $v$, and $s$ ($1 \leq u, v \leq n$, $-10^9 \leq s \leq 10^9$), meaning there is a direct bridge from island $u$ to island $v$ that changes your overall stench by $s$. It is guaranteed that $u \neq v$, and that there is at most one direct bridge from $u$ to $v$ (but there can also be another direct bridge from $v$ to $u$).

Output a single integer: the minimum stench level you can exit the Bog with, assuming you begin with $0$ stench.