Paths

A graph is made up of a set of nodes and a set of links. One link connects two nodes. Figure 1 shows a simple graph with 4 nodes and 5 links. Every link has a direction, running from its originating node to its destination node, and every link carries a cost. The $m$ nodes of a graph are identified by the integers 0, 1, ..., $m-1$.

A path connects one node to another, moving from node to node along the direction of the links. The length of a path is the number of links it uses, and the cost of a path is the sum of the link costs along it. For a given graph, find the minimum cost among the costs of all shortest paths from Node 0 to Node 1. A shortest path with the minimum cost is called a minimum-cost shortest path.

Figure 1	Figure 2

Look at Figure 1 again. The shortest path from Node 0 to Node 1 is the one-link path 0 → 1 with cost 10. The paths 0 → 2 → 1 and 0 → 3 → 1 are cheaper, but they use two links, so they are longer. The minimum-cost shortest path is therefore 0 → 1.

Figure 2 has two shortest paths of length 2. The path 0 → 3 → 1 costs 4, less than the cost 5 of the path 0 → 2 → 1. The path 0 → 2 → 3 → 1 costs only 3, but it uses three links. The minimum-cost shortest path is therefore 0 → 3 → 1.

The first line contains two integers $m$ and $n$ separated by a space, where $m$ is the number of nodes and $n$ is the number of links. Each of the next $n$ lines describes one link with three integers, with a single space between two adjacent integers. The three integers give, in order, Source-Node, Destination-Node, Link-Cost.

There are at most 100 nodes, numbered from 0 to 99. There are at most 1000 links, and a link cost is between 0 and $2^{15} - 1$.

Print a single integer, the path cost of a minimum-cost shortest path from Node 0 to Node 1.

There may be several minimum-cost shortest paths, but they all have the same cost.