题目描述

阿里这学期选修了计算机组织与架构课程。他了解到指令之间可能存在依赖关系，比如WAR(读后写)、WAW、RAW。 如果两个指令之间的距离小于安全距离，就会产生危险，可能导致错误的结果。因此，我们需要设计专门的电路来消除危害。然而，解决这个问题最简单的方法是添加气泡(无用的操作)，这意味着浪费时间来确保两个指令之间的距离不小于安全距离。 两个指令之间的距离的定义是它们开始时间之间的差。 现在我们有很多指令，我们知道指令之间的依赖关系和安全距离。我们也有一个非常强大的CPU与无限的核心数量，所以你可以运行许多指令，你想要同时，CPU是如此之快，它只是花费1ns来完成任何指令。 你的工作是重新排列指令，使CPU可以用最少的时间完成所有的指令。

输入格式

第一行有两个整数N, M (N 以下M行，每一行包含三个整数X, Y, Z，表示X和Y之间的安全距离为Z, Y应该在X之后运行。指令编号从0到N - 1。

输出格式

打印一个整数，CPU运行所需的最小时间。

5 2
1 2 1
3 4 1

2

提示

原题是hdu上的4109http://vjudge.net/problem/HDU-4109