How to Create a Good Game

A video game company called ICPC (International Company for Playing and Competing) is developing a new arcade game. The new game has many branches. This makes the game enjoyable for everyone, since players can choose their routes depending on their skill. Rookie players can pick an easy route to enjoy the game, and talented players can pick their favorite routes to get high scores.

In the game, many checkpoints are connected by paths. Each path consists of several stages, and completing the stages on a path leads players to the next checkpoint. The game ends when players reach a particular checkpoint. At some checkpoints, players can choose which way to go, so routes diverge there. Sometimes different routes join together at a checkpoint. The paths between checkpoints are directed, and there is no loop (otherwise, players could play the game forever). In other words, the structure of the game is a DAG (directed acyclic graph) when paths between checkpoints are viewed as directed edges.

Recently, the development team completed the beta version of the game and received feedback from other teams. It was quite positive overall, but some comments had to be taken into consideration. Some testers pointed out that some routes were very short compared to the longest ones. Indeed, in the beta version, the number of stages in one play can vary drastically depending on the route. Game designers complained that many of their brilliant ideas went unused in the beta version because of the tight development schedule. They wanted more stages in the final product.

However, adding more stages is not easy. This is an arcade game, and if the playing time were too long, it would bring down the income of the game and the owners of arcades would complain. So the longest route of the final product cannot be longer than that of the beta version. Moreover, the producer of the game did not want to change the structure of paths (how the checkpoints connect to each other), since that would require rewriting the scenario, recording voices, and creating new cutscenes.

Considering all of this, the producer decided to add as many new stages as possible while keeping the maximum possible number of stages in one play and the structure of paths unchanged. How many new stages can be added to the game?

N M
x1 y1 s1
.
.
.
xM yM sM

The first line of the input contains two positive integers N and M (2 ≤ N ≤ 100, 1 ≤ M ≤ 1000). N is the number of checkpoints, including the opening and ending of the game. M is the number of paths between checkpoints.

The following M lines describe the structure of paths in the beta version of the game. The i-th line contains three integers xi, yi, and si (0 ≤ xi < yi ≤ N - 1, 1 ≤ si ≤ 1000), which describe that there is a path from checkpoint xi to yi consisting of si stages. As for indices of the checkpoints, 0 indicates the opening of the game and N - 1 indicates the ending of the game. You can assume that, for every checkpoint i, there exists a route from the opening to the ending that passes through checkpoint i. You can also assume that no two paths connect the same pair of checkpoints.

Output a line containing the maximum number of new stages that can be added to the game under the following constraints:

• You cannot increase the maximum possible number of stages in one play (the length of the longest route to the ending).
• You cannot change the structure of paths (how the checkpoints connect to each other).
• You cannot delete any stage that already exists in the beta version.