题目描述

带权有向无环图 $G$ 包含 $n$ 个顶点，编号依次为 $1$ 到 $n$。请计算从顶点 $1$ 到顶点 $n$ 的最长路径长度。

输入格式

第一行输入整数 $n,m$，分别为顶点数与边数。

从第 $2$ 行至第 $m+1$ 行，每行给出 $u,v,w$，表示图中有一条从 $u$ 指向 $v$、权值为 $w$ 的边。保证 $u<v$。

输出格式

输出最长路径长度；若从顶点 $1$ 无法到达顶点 $n$，输出 -1。

2 1
1 2 1

1

说明/提示

原题的分档数据范围如下。