你正在玩“骗子，骗子”游戏。在这个游戏中，$N$ 个人陈述关于某个主题的事实：其中 $N-1$ 个人陈述的是事实，而剩下的一人说了谎。如果你能根据他们陈述的事实找出谁是骗子，你就赢了。

这次游戏的主题是 $K$ 座山的高度，编号为 $1$ 到 $K$。在 $N$ 个人中，第 $i$ 个人说：“山 $a_i$ 比山 $b_i$ 高 $x_i$ 米”。如果你从 $N$ 个人中排除掉骗子，其余 $N-1$ 个人陈述的事实之间不存在矛盾。另一方面，如果你排除掉一个不是骗子的人，那么其余 $N-1$ 个人陈述的事实必然会产生矛盾。

你的任务是编写一个程序，根据 $N$ 个人陈述的事实，找出谁是骗子。

输入格式

第一行包含两个整数，人数 $N$ ($2 \le N \le 200\,000$) 和山的总数 $K$ ($3 \le K \le 200\,000$)。

接下来的 $N$ 行表示 $N$ 个人陈述的事实。第 $i$ 行包含三个整数 $a_i$ ($1 \le a_i \le K$)，$b_i$ ($1 \le b_i \le K$) 和 $x_i$ ($1 \le x_i \le 10^9$)，表示第 $i$ 个人说：“山 $a_i$ 比山 $b_i$ 高 $x_i$ 米”。你可以假设 $a_i \neq b_i$。此外，对于所有 $1 \le i < j \le N$，满足 $(a_i, b_i) \neq (a_j, b_j)$ 且 $(a_i, b_i) \neq (b_j, a_j)$。输入保证存在唯一一名骗子。

输出格式

输出一行，包含一个整数 $i$，表示第 $i$ 个人是骗子。

样例

样例输入 1

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

样例输出 1

3

样例输入 2

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

样例输出 2

6