测试数据来自 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 变量。