Longest Path in a Directed Graph with Cycle Detection

You are given a directed graph with N nodes and M edges. Each edge is represented by three integers u, v and w, which means there is an edge from node u to node v with weight w.

Your task is to determine the weight of the longest path starting from node 1. If the graph contains a cycle, then the answer is INF.

More formally, given a directed weighted graph, find the maximum value of \[ dist(v) = \max_{\textrm{paths from }1 \textrm{ to } v} \sum_{e \in \textrm{path}} w(e) \] for all reachable nodes v. If there is any cycle in the graph, output "INF".

Note: It is guaranteed that if there is no cycle, the longest path is well-defined.

inputFormat

The first line contains two integers N and M, representing the number of nodes and edges, respectively.

The following M lines each contain three space-separated integers: u, v and w, which denote an edge from node u to node v with weight w.

Input Format:

N M
u1 v1 w1
u2 v2 w2
... 
uM vM wM

outputFormat

If the graph contains a cycle, output INF (as a string). Otherwise, output a single integer representing the weight of the longest path starting from node 1.

Output Format:

result

## sample

5 6
1 2 10
2 3 10
3 4 10
4 5 10
1 5 30
3 1 20

INF