Minimal Marathon Distance

You are given a directed acyclic graph (DAG) representing locations and one-way paths between them. The graph has n locations numbered from 0 to n-1. Each directed path is represented by a triple (u, v, d) indicating a path from location u to location v with distance d.

Your task is to compute the minimal distance required to travel from location 0 to location n-1. It is guaranteed that the input graph is a DAG so that a valid topological ordering exists. The minimum distance is defined as the sum of distances along a path where the total sum is minimized.

Mathematically, if we let \(d(u,v)\) denote the distance from node \(u\) to node \(v\), the answer is:

\[ d_{min} = \min \{ \sum_{(u,v) \in P} d(u,v) \mid P \text{ is a path from } 0 \text{ to } n-1 \}. \]

inputFormat

The input is given via standard input (stdin) and has the following format:

n m
u1 v1 d1
u2 v2 d2
... 
um v m d m

Where:

• n is an integer representing the number of locations.
• m is an integer representing the number of paths.
• Each of the following m lines contains three integers: u, v, and d representing a directed path from location u to location v with distance d.

outputFormat

Output a single integer via standard output (stdout): the minimal distance required to travel from location 0 to location n-1.

## sample

3 2
0 1 2
1 2 3

5