Migrated from Lutece 740 XHXJ与麻将

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

XHXJ不仅是个可爱的妹纸，而且麻将也打得非常好，XHXJ想让你得多少点你就得多少点，一切都在她的操控之中，现在XHXJ约上了mzry，又叫上了$n-2$个人一起打麻将，为了不显示自己太厉害，又要展示出自己其实麻将还是打得很不错的。于是XHXJ决定操控麻将局势使得每个人的得分以达到他的要求，当然XHXJ必须是妥妥的一位（即得分最高者），求XHXJ最多可以比mzry多多少分，其中XHXJ编号为$n$（为了低调），mzry编号为$1$（因为傲娇），当然XHXJ是很低调的，在任何情况下她都不会比mzry多得$10^9$以上的分数。

Input

包含多组数据。对于每组数据第一行包含两个数$n$和$m$（$4\le n\le 30000$，$0 < m\le 150000$），即参与打麻将的人数，以及XHXJ在控制分数时需要注意的条件数。接下来的$m$行，每行包含三个数$a,b,c$，表示$b$比$a$高出的得分数不能超过$c$

Output

包含一个正整数，即XHXJ最多可以比mzry高多少分

Samples

2 2
1 2 5
2 1 4

5

Resources

2013 UESTC ACM Training for Graph Theory