AT_abc061_d.[ABC061D] Score Attack

有一个包含 $N$ 个顶点和 $M$ 条带权有向边的有向图。
第 $i$ 条边（$1 \leq i \leq M$）连接顶点 $a_i$ 到顶点 $b_i$，权值为 $c_i$。
利用这个图和棋子，进行如下的一人游戏。

最开始，将棋子放在顶点 $1$，玩家的分数为 $0$。
玩家可以按照以下规则不断移动棋子：

• 当棋子在顶点 $a_i$ 时，可以通过第 $i$ 条边移动到顶点 $b_i$。移动后，玩家的分数增加 $c_i$。

只有当棋子在顶点 $N$ 时，游戏才能结束。
保证在给定的有向图中，存在从顶点 $1$ 到顶点 $N$ 的路径。

当玩家采取使游戏结束时分数尽可能大的策略时，游戏结束时的分数会是多少？
如果游戏结束时的分数可以无限大，请输出 inf。

输入以如下格式从标准输入读入：

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

如果游戏结束时的分数可以无限大，输出 inf；否则输出游戏结束时分数的最大值。

限制条件

• $2 \leq N \leq 1000$
• $1 \leq M \leq \min(N(N-1), 2000)$
• $1 \leq a_i, b_i \leq N\ (1 \leq i \leq M)$
• $a_i \neq b_i\ (1 \leq i \leq M)$
• $a_i \neq a_j$ 或 $b_i \neq b_j\ (1 \leq i < j \leq M)$
• $-10^9 \leq c_i \leq 10^9\ (1 \leq i \leq M)$
• $c_i$ 为整数。
• 给定的图保证存在从顶点 $1$ 到顶点 $N$ 的路径。

样例解释 1

将棋子移动到顶点 $N=3$ 的路径有以下两种：

• 顶点 $1$ → 顶点 $2$ → 顶点 $3$：分数 $4+3=7$
• 顶点 $1$ → 顶点 $3$：分数 $5$
  因此，游戏结束时分数的最大值为 $7$。

样例解释 2

通过不断执行“顶点 $1$ → 顶点 $2$ → 顶点 $1$ → 顶点 $2$ …”的操作，可以让游戏结束时的分数无限增加。

由 ChatGPT 4.1 翻译