题目描述

有一个有 $N$ 个顶点和 $M$ 条边的有向图。第 $i$ 条边 $(1≤i≤M)$ 从顶点 $a_i$ 指向顶点 $b_i$，并且具有权重 $c_i$。我们将使用该图和一个棋子进行以下单人游戏。

初始时，棋子放置在顶点 $1$ 上，玩家的得分设置为 $0$。玩家可以根据以下规则移动棋子：

• 当棋子放置在顶点 $a_i$ 上时，将棋子沿第 $i$ 条边移动到顶点 $b_i$。完成此次移动后，玩家的得分增加 $c_i$。

玩家只能在棋子放置在顶点 $N$ 上时结束游戏。给定的图保证可以从顶点 $1$ 到达顶点 $N$。

当玩家通过最佳策略在游戏结束时使得得分最大化时，最终得分是多少？如果可以无限增加得分，请输出 inf。

约束条件

• $2≤N≤1000$
• $1≤M≤\min(N(N-1),2000)$
• $1≤a_i,b_i≤N (1≤i≤M)$
• $a_i≠b_i (1≤i≤M)$
• $a_i≠a_j$ 或 $b_i≠b_j (1≤i<j≤M)$
• $-10^9≤c_i≤10^9 (1≤i≤M)$
• $c_i$ 是一个整数。
• 在给定的图中，从顶点 $1$ 到顶点 $N$ 存在一条路径。

输入

输入以以下格式从标准输入中给出：

$N$ $M$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$ $:$
$a_M$ $b_M$ $c_M$

输出

如果可以有限地增加得分，请输出游戏结束时可能的最大得分。如果可以无限增加得分，请输出 inf。

示例输入 1

3 3
1 2 4
2 3 3
1 3 5

示例输出 1

7

有两种方式将棋子移动到顶点 $N=3$：

• 顶点 $1$ → 顶点 $2$ → 顶点 $3$：得分 $4+3=7$
• 顶点 $1$ → 顶点 $3$：得分 $5$

因此，在游戏结束时可能的最大得分是 $7$。

示例输入 2

2 2
1 2 1
2 1 1

示例输出 2

inf

通过在顶点 $1$ 和 $2$ 之间交替移动，可以无限增加得分。

示例输入 3

6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000

示例输出 3

-5000000000