题目描述

给定一个 $n$ 个人，和 $m$ 条带权的单向的消息传递方式。

初始第 $1$ 个人得到了一个消息，接下来他需要将信息传递给所有人。

每个人每个时刻可以沿着一条传递方式向另一个人进行通信。具体来说，对于一条从 $u_i$ 指向 $v_i$，权为 $w_i$ 的消息传递方式。如果第 $u_i$ 个人已经知道了消息，则他可以占用连续的 $w_i$ 个单位的时间告知 $v_i$。

注意：

1. 每个人每时每刻只可以和一个人进行通信，即不能同时将消息传递给两个人。
2. 同一时刻可以有多个人进行通信。

现在你想知道至少多少个单位的时间后所有人能得到消息？如果无法告知所有人输出 $−1$。

输入格式

第一行一个正整数和一个非负整数 $n,m$。

接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$。

输出格式

一行一个非负整数表示答案。

输入输出样例 #1

6 7
1 2 1
1 3 1
1 4 1
2 5 1
3 5 1
4 5 1
5 6 1

3

输入输出样例 #2

10 90
9 10 3142695
2 1 6693570
1 6 434001
10 2 5627467
3 1 9978910
4 3 1066840
10 8 3061175
4 10 2299999
8 2 1619176
9 6 8336509
9 2 4786158
8 4 4334534
9 3 1595755
1 4 291244
9 4 7676308
3 2 8396259
1 8 313107
10 6 2937309
6 8 3111052
5 2 9700304
3 7 146217
5 1 447213
4 5 6385205
4 8 2947921
6 1 5237478
6 2 925611
2 7 9267174
5 9 7761759
4 1 9122705
3 5 8275071
4 6 8744772
2 10 2236820
4 7 3203776
7 9 3265731
9 1 5687712
8 3 6691097
5 10 5071499
6 10 6801471
6 3 9431892
5 6 3725839
2 8 4267777
6 5 9422959
10 1 1825674
5 3 7698327
3 6 7856954
6 7 685411
5 4 3383800
1 10 1588586
10 4 4407258
7 6 506727
7 2 1472204
2 9 4408081
7 10 4108745
6 4 9298197
7 1 9146232
3 4 663811
10 9 2226430
3 9 7548536
4 2 4983618
8 5 7899705
6 9 6428184
10 3 3731699
4 9 7250258
1 2 4681565
7 3 3794271
8 9 4969710
2 3 8668136
8 1 5241179
7 5 9136657
7 4 4777912
5 7 5695547
8 7 96356
7 8 940168
10 7 8522236
8 10 6033602
3 10 4238578
1 5 7162734
9 8 6670106
2 6 5173769
2 4 4200175
8 6 2748528
9 7 1672993
1 7 9660115
2 5 4018674
3 8 7177330
10 5 3725568
9 5 4496979
1 3 8508877
5 8 5084427
1 9 5349864

5314154

说明/提示

【样例解释 #1】

• 时刻 $1$：$1\to 2$ 传递信息。
• 时刻 $2$：$2\to 5$ 传递信息；$1\to 3$ 传递信息。
• 时刻 $3$：$1\to 4$ 传递信息；$5\to 6$ 传递信息。

【数据范围】

对于所有测试点，满足 $1\le n\le 14$，$0\le m\le n(n-1)$，$1\le u_i,v_i\le n$，$1\le w_i\le 10^7$。

保证 $u_i\ne v_i$ 且 $\forall 1\le i\lt j\le m$，$(u_i,v_i)\ne (u_j,v_j)$。

\begin{array}{|c|c|c|} \hline \textbf{子任务编号} & n\le & \textbf{分值} \\ \hline 1 & 6 & 20\\ \hline 2 & 10 & 30\\ \hline 3 & 14 & 50\\ \hline \end{array}