The Admiral

Time limit1sMemory limit128 MB

Summary

Find two vertex- and edge-disjoint (except at endpoints) directed paths from node 1 to node v in a weighted graph minimizing total edge weight, which requires a min-cost flow formulation with vertex splitting.

Level: Hard8 of 10
Topics: Shortest path, Graph, Greedy
Solved: No attempts yet

Statement

Michiel de Ruyter is the most famous admiral in the history of the Netherlands. He distinguished himself in the Anglo-Dutch Wars of the 17th century.

Graph theory began to be studied during de Ruyter's lifetime, and the admiral often applied it to his naval battle plans. Each intermediate point at sea is represented as a vertex, and every sea route leading from one point to another is a directed edge. Between two points $u$ and $w$ there is at most one route $u \to w$ . The weight of each edge is the number of cannonballs that must be fired to pass along that route safely.

De Ruyter's most famous tactic is the "De Ruyter Manoeuvre". In it, two warships leave a single point heading in different directions. Each ship moves while fighting enemy vessels, and the two reunite at the destination. The two ships must always choose non-overlapping routes: apart from the start and the destination, they may not pass through the same intermediate point or use the same route.

De Ruyter dislikes wasting money, so he wants to choose the two ships' routes so that the total number of cannonballs fired is as small as possible.

Input

The input consists of several test cases. The end of the input is marked by end-of-file (EOF).

The first line of each test case contains the number of intermediate points $v$ and the number of routes $e$ ( $3 \le v \le 1000$ , $3 \le e \le 10000$ ). Each of the next $e$ lines contains the description of a route $a_i$ , $b_i$ , $c_i$ ( $1 \le a_i, b_i \le v$ , $a_i \ne b_i$ , $1 \le c_i \le 100$ ). Here $a_i$ is the starting point of the route, $b_i$ is its ending point, and $c_i$ is the number of cannonballs that must be fired to travel along it.

The tactic starts at point $1$ and ends at point $v$ . There are always at least two non-overlapping paths between points $1$ and $v$ .

Output

For each test case, print on its own line the minimum total number of cannonballs the two warships must fire while following the tactic.

Note

In the first test case the two ships (red and blue) start at point $1$ and meet at point $6$ . The red ship travels $1 \to 3 \to 6$ ( $33$ cannonballs) and the blue ship travels $1 \to 2 \to 5 \to 4 \to 6$ ( $53$ cannonballs). Apart from the start and the end, the two paths share no vertex or edge, and the total is $86$ cannonballs.

Examples4

Example 1

Input

Expected output

86
11

Example 2
Input
```
3 3
1 2 1
2 3 1
1 3 1
```
Expected output
```
3
```
Example 3
Input
```
4 4
1 2 5
2 4 5
1 3 7
3 4 7
```
Expected output
```
24
```
Example 4
Input
```
4 5
1 2 1
2 3 1
3 4 1
1 3 3
2 4 3
```
Expected output
```
8
```