给定一个 n 个点，m 条边的简单无向连通图。我们想要知道，对于每条边e，在其他最多只有一条边的权值可变为任意值的情况下，我们可以调整边e的权值，能够使得它一定在图的所有最小生成树之中，求我们可以设置这个边e的权值的最大值。

从文件tree.in中读入数据。
第一行包含2个数字n、m。
接着m行，每行3个数字u、v、w，表示u和v之间有一条权值为w的边。

输出到文件tree.out中。
输出m个数字，第i个数字对应输入的第i条边，为这条边允许的最大权值，如果任意值都可以，则输出-1。

【样例1解释】
图如下所示，每条边允许的最大权值分别是4、4、4、3、4、3。

对于第1条边u=3，v=2，w=9来说，权值改为4后，不论我们怎么修改一条边的权值，都是最小生成树的边。如果我们把权值改为5，虽然此时只有唯一的最小生成树，但是如果变化u=1，v=2，w=8的边的权值为1，此时最小生成树有不同的两种，不能保证这条边，一定在最小生成树中。

对于第二条边u=2，v=4，w=15来说，权值改为4后，不论我们怎么修改一条边的权值，都是最小生成树的边。如果我们把权值改为5，如果变化u=1，v=2，w=8的边的权值为1，此时最小生成树有不同的两种，不能保证这条边，一定在最小生成树中。

对于第3条边u=1，v=2，w=8来说，权值改为4后，不论我们怎么修改一条边的权值，都是最小生成树的边。如果我们把权值改为5，如果变化u=2，v=4，w=15的边的权值为1，此时最小生成树有不同的两种，不能保证这条边一定在最小生成树中。

对于第4条边u=1，v=3，w=5来说，权值改为3后，不论我们怎么修改一条边的权值，都是最小生成树的边。如果我们把权值改为4，如果变化u=1，v=4，w=14的边的权值为1，此时最小生成树有不同的两种，不能保证这条边一定在最小生成树中。

【样例2解释】
输入的图正好是一棵树，所以任意设置边的权值，这些边永远都在最小生成树中。

【数据范围】
对于所有测试数据有：$1≤n≤2×10^5,n-1≤m≤2×10^5,1≤w<10^9$。保证图中没有重边和自环。保证所有点之间互相连通。除特殊性质B外，均保证原图的最小生成树唯一。

特殊性质A：n-1=m
特殊性质B：对于任意的边的编号i，j，均满足$w_i=w_j$
特殊性质C：图中对于任意的点$i(i<n)$，均有一条和i+1的边，边的权值为1
特殊性质D：图中有n条边，每条边均满足$u=v % n+1$

附件：tree1.ans 附件：tree1.in 附件：tree2.ans 附件：tree2.in 附件：tree3.ans 附件：tree3.in