暂无测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

KC 正在从家（编号为1）赶向学校，但是他的脑子有点问题，总是喜欢走最长路到学校，现在他的路上有 n 个点， m 条有向边，KC 并不会走一条从家里到不了学校（编号为 n）的路，但是如果他走的路上有一个能无尽走下去的路且脑子正常的人都可以直接走到学校时(即便他这个能无尽走下去的路上有学校)，他就会无尽走下去，此时你要输出"It's too late."，如果不存在一条路径到达学校，输出-1，如果能到达学校，输出最长路的长度。

Format

Input

第一行输入两个正整数，表示 n,m。
下面 m 行，每行输入三个正整数，表示一个有向边的起点，终点，长度(用字母表示为 x,y,z)。

Output

输出答案

Sample 1

Input

4 3
1 2 3
1 3 3
2 3 3

Output

-1

Sample 2

Input

7 4
1 2 1
2 3 1
3 1 1
3 7 1

Output

It's too late.

Limitation

1 \(\le\) n \(\le\) 3 \(\times\) 10^5
1 \(\le\) m \(\le\) \( \max(3 \times 10^5,n \times (n-1)) \)

1 \(\le\) x,y,z \(\le\) n