Description

有一个n个点m条边的连通无向图（无重边、无自环），点的编号为1~n。每条边都有一个正的边权，并且每条边边权互不相同（即数据保证该图的最小生成树唯一）。
如果只是求最小生成树，那么Ohyee觉得太简单了，于是他决定考考你。
对于每条边(u,v)都进行询问：
——如果该边在最小生成树上，那么输出“Ohyee”；
——如果该边不在最小生成树上，那么输出最小生成树上u,v两点路径中边权的最小值。

Format

Input

第一行输入两个整数n,m(2<=n<=100000,n-1<=m<=200000)
接下来m行，每行输入三个整数u,v,w。u,v表示该边连接点的编号，w是边权。
(1<=w<=1000000000)

Output

输出一共m行，按照输入的边的顺序回答每条边的询问。

Sample 1

Input

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

Output

Ohyee
Ohyee
2
Ohyee

Limitation

1s 256MB

Hint

原图最小生成树中的边是(1,2,2) (2,3,5) (4,1,3)
对于输入的第三条边(3,4,7)，树上3->4的路径是3->2->1->4，边权分别是5,2,3，最小值是2。