【题目描述】

给定一张包含 $n$ 个点和 $m$ 条边的简单连通无向图．点的编号为 $1,2,\ldots,n$，第 $i$ 条边连接 $u_i,v_i$，边权为 $w_i$．

一个简单环是一个首尾相接的点序列，除起点与终点相同外，环上的其他点互不相同．一个简单环的瓶颈值定义为环上所有边权的最大值．

对于每个点 $x$，请在所有包含点 $x$ 的简单环中，求出瓶颈值的最小值．如果不存在包含点 $x$ 的简单环，则该点的答案为 $-1$．

---

【输入描述】

第一行输入两个整数 $n,m$，分别表示点数和边数．

接下来的 $m$ 行，每行输入三个整数 $u_i,v_i,w_i$，表示一条连接点 $u_i$ 和点 $v_i$、边权为 $w_i$ 的无向边．

保证给出的图是简单连通无向图．

---

【输出描述】

输出一行 $n$ 个整数，其中第 $x$ 个整数表示点 $x$ 的答案．

---

【样例 1】

【样例 1 输入】

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

【样例 1 输出】

5 5 5 6 6 -1

【样例 1 解释】

点 $1,2,3$ 所在的环 $1\to2\to3\to1$ 的瓶颈值为 $5$．点 $3,4,5$ 所在的环 $3\to4\to5\to3$ 的瓶颈值为 $6$．

点 $3$ 同时位于两个环中，因此选择瓶颈值较小的第一个环，答案为 $5$．点 $6$ 不属于任何简单环，答案为 $-1$．

---

【样例 2】

【样例 2 输入】

4 3
1 2 7
2 3 1
3 4 9

【样例 2 输出】

-1 -1 -1 -1

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans．

该样例满足 $n\le80$，$m\le150$．

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans．

该样例满足图中不同边权的数量不超过 $10$．

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans．

该样例满足 $m-n+1\le20$．

---

【样例 6】

见选手目录下的 Data/sample6.in 和 Data/sample6.ans．

该样例满足 $n,m\le3000$．

---

【样例 7】

见选手目录下的 Data/sample7.in 和 Data/sample7.ans．

该样例无特殊限制．

---

【数据规模与约定】

对于所有测试数据，保证：

• $2\le n\le2\times10^5$；
• $n-1\le m\le4\times10^5$；
• $1\le u_i,v_i\le n$ 且 $u_i\ne v_i$；
• $1\le w_i\le10^9$；
• 图中不存在重边；
• 给出的图连通．

子任务编号	分数	特殊性质
$1$	$10$	$n\le80$，$m\le150$
$2$	$15$	图中不同边权的数量不超过 $10$
$3$		$m-n+1\le20$
$4$	$20$	$n,m\le3000$
$5$	$40$	无特殊性质

各子任务独立计分．只有通过一个子任务中的全部测试点，才能获得该子任务的分数．

---

【大样例下载链接】

点击下载本题选手目录