You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1673 题。

题目描述

你玩一个包含 $n$ 个房间和 $m$ 条隧道的游戏。你从初始分数 $0$ 开始，每次通过一条隧道会使你的分数增加 $x$，其中 $x$ 可以是正数也可以是负数。你可以多次通过同一条隧道。

你的任务是从房间 $1$ 移动到房间 $n$。请你计算能够获得的最大分数。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示房间的数量和隧道的数量。房间编号从 $1,2,…,n$。

接下来有 $m$ 行，每行描述一条隧道。每行包含三个整数 $a$, $b$ 和 $x$：表示一条从房间 $a$ 到房间 $b$ 的隧道，分数增加值为 $x$。所有隧道都是单向的。

你可以假设从房间 $1$ 到房间 $n$ 是可达的。

输出格式

输出一个整数：你能够获得的最大分数。如果可以获得无限大的分数，则输出 $−1$。

样例

4 5
1 2 3
2 4 -1
1 3 -2
3 4 7
1 4 4

5

说明/提示

$1 \leq n \leq 2500$；

$1 \leq m \leq 5000$；

$1 \leq a,b \leq n$；

$-10^9 \le x \le 10^9$。