Longest Path in a Directed Graph

Given a directed graph with N checkpoints numbered from 0 to N-1 and M roads connecting these checkpoints, each road is represented by a triple [start, end, length]. Your task is to determine the longest path from checkpoint 0 to checkpoint N-1. If no such path exists, output -1.

Note: It is guaranteed that the graph does not contain cycles that can increase the path arbitrarily. All road lengths are positive integers.

The answer should be computed using an algorithm that reads input from standard input (stdin) and outputs the answer to standard output (stdout). Use the following input format.

inputFormat

The first line of input contains two integers N and M separated by a space, where N is the number of checkpoints and M is the number of roads.

The next M lines each contain three integers u, v and w separated by spaces, representing a road from checkpoint u to checkpoint v with length w. Checkpoints are numbered from 0 to N-1.

outputFormat

Output a single integer which is the length of the longest path from checkpoint 0 to checkpoint N-1. If there is no such path, output -1.

4 5
0 1 2
0 2 4
1 2 1
1 3 7
2 3 3

9