예약 시각 메모 검증

문제

병원 접수 직원이 N건의 예약에 대해 시각 관계를 메모로 남긴다. 각 예약의 시작 시각은 정수(분 단위, 음수도 허용하며 범위 제한은 없다)인 미지수 t_1, ..., t_N이다. 메모는 모두 M개이며 순서대로 적혀 있다. k번째 메모는 정수 a_k, b_k, d_k로 이루어지고 'b_k번 예약의 시각은 a_k번 예약의 시각보다 정확히 d_k분 뒤이다', 즉 t_{b_k} - t_{a_k} = d_k라는 뜻이다. d_k는 음수나 0일 수 있고, a_k와 b_k가 같을 수도 있다. 또한 메모로 직접 또는 간접적으로 시각 차이가 정해지는 예약들은 같은 묶음이며, 한 묶음의 예약은 모두 길이 T분의 하나의 진료 시간대 안에 들어가야 한다. 즉 한 묶음에서 가장 늦은 예약 시각과 가장 이른 예약 시각의 차이는 T 이하여야 한다. 서로 다른 묶음은 독립이어서 묶음마다 시각을 통째로 자유롭게 평행 이동할 수 있다. 메모에 한 번도 등장하지 않은 예약은 혼자인 묶음이다. 앞에서부터 k개의 메모를 모두 만족하면서 위 시간대 조건도 지키는 시각 배정이 존재하지 않게 되는 가장 작은 k를 구한다. 처음 M개의 메모를 모두 만족하는 배정이 존재하면 0을 출력한다.

입력

첫 줄에 정수 N, M, T가 공백으로 구분되어 주어진다. 이어지는 M개의 줄에 k번째 메모의 a_k, b_k, d_k가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ M ≤ 200,000, 0 ≤ T ≤ 10^12, 1 ≤ a_k, b_k ≤ N, |d_k| ≤ 2,000,000이다. 모든 값은 정수이다.

출력

조건을 처음으로 만족할 수 없게 되는 메모의 번호 k를 한 줄에 출력한다. 끝까지 만족할 수 있으면 0을 출력한다.

4 4 10
1 2 3
2 3 4
1 3 7
3 4 5

4

3 3 100
1 2 5
2 3 5
1 3 11

3

2 2 5
1 2 5
2 1 -5

0

출처: Devin.KR 자체 제작