配点 : 400 点
問題文
在帕肯王国 N 村庄和 M 有一条真正的路。 i\ (1 \le i \le M) 主要道路是村庄 A_i, B_i 双向连接,可以在任何状态下交叉。 需要 1 分钟。
起初,所有道路都被冰覆盖。 在 C_i = -1 的情况下,冰不会融化; 对于 1 \le C_i , C_i 分钟后冰将会融化。
国王帕肯最初住在一个村庄里。 如果你在 1 ,你可以通过一些道路到达村庄。 我想转到 N 。帕肯也可以在任何村庄等待。而且,由于帕肯比较谨慎,所以他尽量不想走在结冰的路上。尽量减少在结冰道路上花费的时间 求移动到 N 所需的最短时间。
然而,该村 1 空村 保证您可以通过多条路到达 N 。 可通过多条道路到达制約
- 2 \leq N \leq 2\times 10^5
- N-1 \leq M \leq \min(\frac{N(N-1)}{2} , 2\times 10^5)
- 1 \le A_i < B_i \le N
- 1 \le i < j \le N , 当我输入 (A_i,B_i)\neq (A_j,B_j)
- C_i=-1 或 至少 1 \le C_i \le 10^9
- 所有输入均为整数
- 村 1 空村 保证您可以通过多条路到达 N 。
入力
输入是按以下格式从标准输入给出的。
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
出力
打印所用时间的最小值(以分钟为单位)。
入力例 1
3 3 1 3 -1 1 2 3 2 3 1
出力例 1
5
村 1 直接从村庄 如果转到 3 ,则需要的时间是 需要 1 分钟,但肯定要经过冰路。 然而,该村 通过 2 ,可以避开冰路,到达村庄。 您可以前往 3 。在本例中,Paken 是一个村庄 您必须等待 1 在 3 分钟。
入力例 2
4 5 1 2 1 2 4 -1 1 3 -1 3 4 3 2 3 3
出力例 2
5