测试数据来自 MYOJ/1014

背景

• Idea: limingyang
• Data: limingyang
• Solution: limingyang
• 题面: limingyang + oistream

不美观的 $\LaTeX$ 已经被修正。

被防盗链的图片已经被修正。

语病已经被修正。

描述

NOIP 的人数不断增加，工作人员不堪重负，然后失去了控制！

CCF 的考试机制是建立在老版 NOIP 的基础上的，而 NOIP 的少量资金已经不支持大量 OIer 在同一时间内进行考试并及时批改试卷。为了让更多的人参加竞赛， CCF 动用了大量资金，创建了 CSP 。

现在，为了警示各位 OIer 远离失控了的 NOIP 考场并前往刚刚建好的 CSP 考场， CCF 发出了一条通告，但有的人不上 CCF 官网，所以也就不知道这条消息。但这条消息得到了 Vijos ，洛谷等 OJ 和许多 OIer 的广泛转发，让我们假设，所有人都会在看到消息的那一瞬间开始转发，但不同的人可能会花上不同的时间。

下面，会有 $n$ 个转发者，编号分别为 $1\sim n$， CCF 编号为 $0$ ，并且有 $m$ 组数据，每一组均会有三个数，分别代表转发者，接收者和转发者转发所消耗的时间。

现在，为了知道最短要多久才能让所有人都接受到消息， CCF 找到了你，要求你在 $1$ 秒内说出答案！

如果无法让所有人都接受到消息，则输出 -1 。

输入格式

第一行有两个整数 $n$ 和 $m$ 。

下面有 $m$ 行，每行有三个整数，分别代表转发者，接收者和转发者转发所消耗的时间。

输出格式

一个数，如果所有人都能接收到消息，则输出让所有人都知道消息所要用的最小时间，否则输出 -1。

样例

输入样例1

5 5
0 1 1
1 2 2
2 3 3
3 4 4
2 5 5

输出样例1

10

数据规模与约定

$1\leq n\leq m\leq 100$。

所有数均为 int 变量。