Longest Path in a Weighted Directed Acyclic Graph

Given a weighted directed acyclic graph (DAG) G with n vertices numbered from 1 to n, design an algorithm to compute the longest path from vertex 1 to vertex n.

The input begins with two integers n and m, representing the number of vertices and edges respectively. The next m lines each contain three integers u, v, and w, indicating there is a directed edge from u to v with weight w. It is guaranteed that the graph is acyclic.

Your task is to output the maximum total weight of any path from vertex 1 to vertex n. You can assume that there is at least one valid path from 1 to n.

inputFormat

The first line contains two integers n and m, where 1 ≤ n ≤ 10⁵ and 0 ≤ m ≤ 10⁶. Each of the following m lines contains three integers u, v, and w, representing a directed edge from vertex u to vertex v with weight w.

outputFormat

Output a single integer, the maximum total weight of any path from vertex 1 to vertex n.

sample

4 5
1 2 3
1 3 2
2 3 2
2 4 4
3 4 4

9