시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB52251337.143%

문제

You are playing "$N-1$ Truths and a Lie" game. In this game, $N$ people say facts about some topic. Each of the $N-1$ people says a true fact but the other person says a lie. You win if you identify who is a liar from the facts they said.

This time, the topic of the game is the heights of $K$ mountains, numbered $1$ through $K$. Among $N$ people, the $i$-th person says "mountain $a_i$ is $x_i$ meters higher than mountain $b_i$". If you exclude a specific liar from $N$ people, the facts that the other $N-1$ people say have no contradiction. On the other hand, if you exclude a person who is not a liar, the facts that the other $N-1$ people say must contradict.

Your task is to write a program to identify who is a liar among $N$ people from the facts they said.

입력

The first line consists of two integers, the number $N$ ($2 ≤ N ≤ 200\,000$) of people and the number $K$ ($3 ≤ K ≤ 200\,000$) of mountains. The following $N$ lines represent facts that $N$ people say. The $i$-th line contains three integers $a_i$ ($1 ≤ a_i ≤ K$), $b_i$ ($1 ≤ b_i ≤ K$), and $x_i$ ($1 ≤ x_i ≤ 10^9$), which represent the $i$-th person says mountain $a_i$ is $x_i$ meters higher than mountain $b_i$. You can assume $a_i \ne b_i$. Also, you can assume $(a_i, b_i) \ne (a_j, b_j)$ and $(a_i, b_i) \ne (b_j, a_j)$hold for all $1 ≤ i < j ≤ N$. The input is consistent with the situation where there is exactly one liar.

출력

Output in a line a single integer $i$, where the $i$-th person is a liar.

예제 입력 1

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

예제 출력 1

3

예제 입력 2

8 5
1 2 4
2 3 1
4 3 2
1 4 3
1 5 1
4 5 7
5 2 3
5 3 4

예제 출력 2

6