26469번 - $N-1$ Truths and a Lie 다국어

문제

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.

제한

힌트