27586번 - Profitable Trip 다국어

You are planning a road trip. You have carefully mapped out all potential waypoints that you may stop at. From each waypoint, there are roads that allow you to drive to other waypoints, but roads can only be used in one direction. In order to alleviate traffic jams, the road planners have decided to require tolls on the more popular roads. The less popular roads may even pay you to drive on them.

As a result, it may be possible to make a profit from the road trip. But there is a catch---your wallet can only hold a maximum of $w$ dollars more than what you have started with. You are allowed to get paid even when your wallet is full, but you will not be able to keep more than $w$ dollars over what you started with. You may assume that whenever you need to pay a toll, you will have money to pay.

What is the maximum profit you can make on your trip?

The first line of input contains three integers $n$, $m$, and $w$ ($1 \leq n, m \leq 2\,000$, $1 \leq w \leq 100$), where $n$ is the number of waypoints, $m$ is the number of roads, and $w$ is the additional capacity of your wallet. The waypoints are numbered $1$ through $n$. The first waypoint ($1$) is the start of your road trip, and the last waypoint ($n$) is the destination.

Each of the next $m$ lines contains three integers $u$, $v$, and $t$ ($1 \leq u, v \leq n$, $-100 \leq t \leq 100$), indicating that there is a road from waypoint $u$ to waypoint $v$, with a gain of $t$ dollars. If $t > 0$, then you are paid $t$ dollars to use the road. If $t < 0$, you must pay a toll of $|t|$ dollars to use the road, resulting in a change of $t$ to your profit. It is guaranteed that $u \neq v$, and there is at most one road from $u$ to $v$ (but there can also be a road from $v$ to $u$).

You may assume that it is possible to reach waypoint $n$ from waypoint 1.

Output a single integer, which is the maximum profit you can make during the road trip. If there is a loss, output the loss as a negative number.