链接: https://cses.fi/problemset/task/1673

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你在一个由 $n$ 个房间和 $m$ 条隧道组成的游戏中。你的初始得分为 $0$，每条隧道会使你的得分增加 $x$，其中 $x$ 可正可负。一条隧道你可以经过多次。

你的任务是从房间 $1$ 走到房间 $n$。你能得到的最高得分是多少？

输入

第一行输入包含两个整数 $n$ 和 $m$：房间数量和隧道数量。房间编号为 $1,2,\dots,n$。

接着有 $m$ 行描述隧道。每行包含三个整数 $a$、$b$ 和 $x$：隧道从房间 $a$ 出发，抵达房间 $b$，并使你的得分增加 $x$。所有隧道都是单向隧道。

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

输出

输出一个整数：你能得到的最高得分。不过，如果你能得到任意大的得分，输出 $-1$。

数据范围

$1 \le n \le 2500$ $1 \le m \le 5000$ $1 \le a,b \le n$ $-10^9 \le x \le 10^9$

样例输入

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

样例输出

5