John 热爱冬天。每个滑雪季，他都会和朋友们去直升机滑雪。为此，他们租了一架直升机，直接飞往阿尔卑斯山的任意一座山峰。从那里开始，他们沿着风景如画的斜坡，穿过未被触碰的积雪滑下。

当然，他们希望只在最好的雪况和最好的天气下滑雪。为此，他们使用了一个综合条件度量，并对每天所有可用的斜坡进行评分。

你能帮他们找到最棒的路线吗？

输入格式

输入包含： 一行，包含两个整数 $n$ ($2 \le n \le 1000$) 和 $m$ ($1 \le m \le 5000$)，其中 $n$ 是斜坡之间连接点（从 1 开始编号）的数量，$m$ 是斜坡的数量。 $m$ 行，每行包含三个整数 $s, t, c$ ($1 \le s, t \le n, 1 \le c \le 100$)，表示一条从点 $s$ 到点 $t$、条件度量为 $c$ 的斜坡。

没有入边的点是风景优美的山顶，没有出边的点是山谷。直升机可以在任何连接点降落，因此朋友们可以从他们想要的任何点开始，并在任何点结束他们的行程。所有的斜坡都是下坡，所以无论他们从哪里开始，在经过任何斜坡后，他们都无法再次回到同一个点。

输出格式

输出一个整数，表示朋友们可以采取的路径上条件度量的最大总和。

样例

图 C.1：第二个样例的地图

样例输入 1

5 5
1 2 15
2 3 12
1 4 17
4 2 11
5 4 9

样例输出 1

40

样例输入 2

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

样例输出 2

7