Description

阿里本学期开设了计算机组成原理课程。他了解到指令之间可能存在依赖关系，例如WAR（写入后读取）、WAW、RAW。

如果两个指令之间的距离小于安全距离，则会导致危险，这可能导致错误的结果。所以需要设计特殊的电路以消除危险。然而，解决此问题的最简单方法是添加气泡（无用操作），这意味着浪费时间以确保两条指令之间的距离不小于安全距离。对两条指令之间距离的定义是它们的开始时间之间的差。

现在有很多指令，已知指令之间的依赖关系和安全距离，可以根据需要同时运行多个指令，并且CPU速度非常快，只需花费1ns即可完成任何指令。你的工作是重新排列指令，以便CPU用最短的时间完成所有指令。

Format

Input

输入包含几个测试用例。每个测试用例的第1行都包含两个整数$N$ 和$M （N ≤1000,M ≤10000）$，表示$N$ 个指令和$M$ 个依赖关系。以下$M$ 行，每行都包含3个整数$X 、Y 、Z$，表示$X$ 和$Y$ 之间的安全距离为$Z$ ，$Y$ 在$X$之后运行。指令编号为$0～N -1$。

Output

单行输出一个整数，即CPU运行所需的最短时间。

Samples

5 2
1 2 1
3 4 1

2