Background

“讲道理，这一届新生颜值不错。”
——来自经院迎新工作组的一致意见。

Description

wbs又当野导带新生游园了，由于新生人数过多（你可以认为是无穷多），他决定把它们进行分组。
他最多带n个组，其中第一组只有一个人，就是wbs。
接下来有m个约束，第i个约束规定第ui组和第vi组不能相差超过wi人。
求wbs最多带多少新生游园，或是指出他可以带无穷多的新生。

Format

Input

第一行两个整数n,m。
接下来m行，第i行包含三个整数ui,vi,wi，意义如题目所述。

Output

如果wbs可以带无穷多新生，请输出"Infinity"（不含引号）。
否则输出一行一个整数，表示最多能带的新生人数。

Sample 1

Input

3 3
1 2 1
2 3 3
1 3 2

Output

5

Limitation

1s, 256MB for each test case.

Hint

对于全部测试数据，n<=500000,m<=1000000,1<=u,v<=n,1<=w<=10^6。
本题共有10个测试数据点，每个数据点满足如下特殊限制：
测试点1：m=n-1，每组最多出现在两条约束中。
测试点2，3：m=n-1且不存在一条约束中ui=vi，任意两组之间最多有一条约束。
测试点4，5：n<=2000。
测试点6：所有的w相等。
测试点7，8：所有的约束随机生成。
测试点9，10：不满足任何特殊限制。

Source

wbs