게으른 아리를 위한 접종 계획

아리와 쿠기가 사는 나라에 고양이 바이러스가 유행해서 고양이들이 백신을 맞아야 한다.

현재 개발된 백신은 N개이고, 각 백신은 1부터 N까지의 번호로 구분한다. 몇몇 백신은 선행관계가 있어서, 어떤 백신을 접종하기 전에 반드시 먼저 접종해야 하는 백신이 존재한다. 이 백신들은 번호가 아주 잘 매겨져 있어서, K번 백신 이전에 접종해야 하는 모든 백신의 번호는 1 이상 K-1 이하이다. 또한, 이전에 접종해야 하는 백신이 없는 경우가 반드시 하나 이상 존재하고, 서로 선행관계가 없는 두개의 백신이라면, 같은 날에 접종할 수 있다.

모든 백신은 접종한 당일을 1일차로 하는 7일의 백신 유효기간이 존재하고, 유효기간의 조건은 다음과 같다. 선행 관계가 있는 백신 중 이후 백신은 이전 백신의 유효기간 내에만 접종할 수 있다. 또한, 이전 백신은 유효기간 내에는 재접종이 불가능하다. 만약, 이전 백신의 유효기간이 지났다면, 이전 백신을 재접종하고, 유효기간 내에 다음 백신을 접종해야 한다. 이때, 선행관계가 있는 두 개의 백신은 같은 날에 접종할 수 없다.

또한, 백신의 부작용을 막기 위해 선행관계가 있는 백신 사이에는 최소 대기기간이 존재한다. 최소 대기기간은 최소 1일부터 최대 100일까지 존재할 수 있는데, 이 기간은 이전 백신을 접종한 날짜를 포함한다. 그리고 다음 백신은 최소 대기기간이 끝난 다음 날 접종할 수 있다. 예를 들어, A 백신과 B 백신 사이의 최소 대기기간이 5일이라면, A 백신 접종 후 6 일차에 B 백신 접종이 가능하다.

모든 백신에 대해 최소 대기기간에 대한 부작용이 성립하지 않는 경우가 존재하는데, 이미 접종한 백신을 재접종할 경우이다. 예를 들어, C 백신과 D 백신 사이에 최소 대기기간이 7일이었다고 하자. C 백신을 접종하고 최소 대기기간이 지난 다음 날이면 C 백신을 접종한 지 8 일차이기 때문에 유효기간이 지났으므로 C 백신을 재접종해야 한다. 재접종할 경우 최소 대기기간을 고려할 필요가 없지만, 선행관계가 존재하는 두 백신은 같은 날 접종할 수 없어서 C 백신을 접종한 지 8 일차에 재접종하고 9 일차에 D 백신을 접종할 수 있다.

쿠기는 백신을 공수해 오느라 바빠서, 아리가 최대한 빨리 모든 백신을 접종할 수 있도록 일정을 계획하기로 했다. 하지만 게으른 아리는 아직도 일정을 계획하지 않았다. 게으른 아리를 대신해서 고양이 한 마리가 최대한 빨리 모든 백신을 접종하는 일정이 총 며칠이 걸리는지 구해주자.

첫째 줄에 백신의 개수 N (1 < N ≤ 10,000)와 백신들의 선행관계 개수 M (1 ≤ M < 100,000)가 주어진다.

둘째 줄부터 M+1번째 줄까지 총 M개의 줄에 각 선행관계의 정보가 세 개의 정수 S,E (1 ≤ S < E ≤ N), W (1 ≤ W ≤ 100)로 주어진다.

S는 이전에 접종해야 하는 백신의 번호, E는 이후에 접종해야 하는 백신의 번호, W는 S를 접종한 후 E를 접종하기까지의 최소 대기기간을 의미한다.

항상 모든 백신을 유한한 시간 안에 접종 할 수 있는 경우만 입력으로 주어진다.

고양이 한 마리가 최대한 빨리 모든 백신 접종을 완료하도록 일정을 계획할 때, 총 며칠이 걸리는지 출력한다.