Longest Path in a Directed Acyclic Graph

You are given a directed acyclic graph (DAG) with \( n \) bus stops (nodes) and \( m \) directed routes (edges). Each route is represented by three integers \( u \), \( v \), and \( w \), which denote a directed edge from bus stop \( u \) to bus stop \( v \) with a travel time of \( w \). Your task is to compute the maximum travel time among all possible paths in the given DAG.

A path's travel time is the sum of the weights (travel times) of the edges along the path. Note that a valid path can start at any bus stop with no incoming routes and does not have to finish at a specific node. Ensure your solution efficiently handles the graph by leveraging its acyclic property.

Hint: You may use topological sorting combined with dynamic programming to solve the problem.

inputFormat

The first line of input contains two space-separated integers \( n \) and \( m \), representing the number of bus stops and the number of routes, respectively.

The following \( m \) lines each contain three space-separated integers \( u \), \( v \), and \( w \), indicating a directed edge from bus stop \( u \) to bus stop \( v \) with a travel time of \( w \).

outputFormat

Output a single integer which is the longest travel time (i.e., the maximum sum of weights along any path) in the DAG.

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

12