Migrated from Lutece 3161 最小生成树？

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一个 $n$ 个点，$m$ 条边的带权无向连通图，求它的最小生成树。

这个问题对于你来说太简单了，于是你想到了一个更难的问题：

对于每一条边，你可以将它的边权修改为一个整数，求出它的边权最大修改为多少时，它仍然在图的所有最小生成树上。如果这条边无论边权是多少都出现在所有最小生成树中，输出 $-1$。（每条边的修改相互独立）

Input

第一行两个正整数 $n,m(2\leq n\leq 2×10^5,n-1\leq m\leq2×10^5)$。

接下来 $m$ 行，每行三个正整数 $u,v,w(1\leq u,v\leq2×10^5,1\leq w\leq10^9)$，表示 $u,v$ 之间有一条边权为 $w$ 的无向边。

数据保证没有重边和自环。

Output

一行 $m$ 个整数，第 $i$ 个数表示第 $i$ 条边修改后的最大边权，如果这条边无论边权是多少都出现在所有最小生成树中，输出 $-1$。

Samples

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

2 -1 3 3

Note

样例中的图如下：

Resources

2024 UESTC ICPC Training for Graph