27567번 - Bog of Eternal Stench 다국어

You are trying to reach the center of a Labyrinth, which means 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 make it through the Bog with the minimum level of stench possible.

Luckily, you have previously determined 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 the starting location of your journey through the Bog of Eternal Stench, and the last is your destination at the other side.

From each island, established bridges allow you to travel to other islands, but these bridges can only be used in one direction. Because this is the Bog of Eternal Stench, traveling along most bridges will increase your overall stench by a specific amount. However, some bridges are quite pleasant, and will decrease your overall stench as you travel along them. But there is a catch---your stench level can never drop below $0$. (A bridge that would decrease your stench level below $0$ sets it to $0$ instead).

You have carefully mapped out all of the islands and bridges, and measured the amount each bridge will increase or decrease your stench. As a result, it may be possible to traverse the Bog of Eternal Stench and emerge with no stench at all!

Your top priority is reaching the destination island with minimum stench; you are willing to take a circuitous path that visits some islands multiple times if doing so achieves this goal. Your path must end at the destination island, but you don't have to leave the Bog immediately the first time you reach your destination, if taking an additional detour and returning to the island later would decrease your final stench value.

The first line of input 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 3 integers $u$, $v$, and $s$ ($1 \leq u, v \leq n$, $-10^9 \leq s \leq 10^9$), indicating that there is a direct bridge from island $u$ to island $v$ that changes your overall stench level 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$).

You may assume that it is possible to reach island $n$ (your destination) from island $1$ (your starting location).

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