Problem H
Mario Kart
Mario and his peers are going racing. The racing circuit they will compete on is complex, as the roads often split into multiple paths. Each road segment may contain different obstacles and boosts that can slow down or speed up the racer, respectively.
Mario really wants to win the race, so he resorts to using data to construct the fastest route to complete a single lap. He has drawn the course on a piece of paper, drawing points and road segments with numbers on them. If the number on a road segment is positive, it means that there are that many more obstacles than boosts on that segment, and vice versa for negative numbers. It is faster for Mario to choose the path where this number is the lowest.
Mario always starts the race at the point $0$. When Mario reaches the same point again, he will have completed a lap.
Find the lowest sum of the differences between boosts and obstacles for a single lap.
Input
The input starts with a line containing two numbers $v, w$ ($3<v<10000, v<=w<500000$), where $v$ is the number of points on the map and $w$ is the number of road segments.
The next $w$ lines contain three numbers, $a, b, c$, where
-
$a<b$ or $a>0 \land b=0$
-
$-50 < c < 2000$
-
$a$ is the number of the point on the map where the road segment starts
-
$b$ is the number of the point on the map where the road segment ends
-
$c$ is the difference between the number of obstacles and boosts.
Output
Output a single integer: the lowest sum of the differences between boosts and obstacles for a single lap.