Longest Path in a Weighted DAG

You are given a weighted Directed Acyclic Graph (DAG) represented by n nodes and m directed edges. Each edge has an associated weight. Your task is to compute the length of the longest path in the graph.

The longest path is defined as the maximum sum of weights along any path. A path can consist of a single node (with a sum of 0) or multiple nodes connected by edges. The graph is guaranteed to have no cycles.

Note: If there are no edges in the graph, the answer is 0.

The input is given via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The input consists of multiple lines. The first line contains two integers, n and m, representing the number of nodes and the number of edges respectively. The following m lines each contain three integers u, v, and w indicating there is a directed edge from node u to node v with weight w.

Nodes are numbered from 0 to n-1.

outputFormat

Output a single integer which is the length of the longest path in the graph.

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

9