Maximum Weight Simple Path

You are given a directed graph with n vertices and m edges. Each edge is associated with a weight. Your task is to compute the maximum possible sum of weights along any simple path in the graph. A simple path is a path that visits each vertex at most once.

Mathematically, if a path is formed by vertices \(v_1, v_2, \dots, v_k\) and the corresponding weights are \(w(v_1,v_2), w(v_2,v_3), \dots, w(v_{k-1},v_k)\), then you need to maximize:

[ \text{Maximum Weight} = \max\left{\sum_{i=1}^{k-1} w(v_i,v_{i+1}) \right} ]

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

inputFormat

The first line of input contains two space-separated integers n and m — the number of vertices and the number of edges respectively.

The next m lines each contain three space-separated integers u, v, and w representing a directed edge from vertex u to vertex v with weight w.

Note: The vertices are 1-indexed.

outputFormat

Output a single integer — the maximum sum of weights on any simple path in the graph. If no path exists (i.e. when there are no edges), output 0.

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

18