题目描述

Sponsor 是市长，他很会修路，但是他退休了，于是他打开了一款城市建造游戏。

一开始城市里面居然没有路！为了最小化市民的通勤时间 不然一堆刁民就会使用其高超的寻路 $a_i$ 把路堵死，Sponsor 在所有通勤路线的起点 $x_i$ 和终点 $y_i$ 之间建立了一条权值 $z_i$ 无向边。建设道路后，城市可以看作 $n$ 个点 $m$ 条带权边的简单无向连通图。没错，又是图。

定义 $x_1 \rightarrow x_2 \rightarrow ... \rightarrow x_k$ 的路径权值是一路上经过的边的边权最大值。$x$ 到 $y$ 的最优路径是所有起点为 $x$ 终点为 $y$ 的路径权值最小值。

一天，Sponsor 的城市发生了天翻地覆的变化，具体的，城市变成了原来的补图，补图上一条边 $u − v$ 的权值即为原图上 $u$ 到 $v$ 的最优路径权值。

但是市民仍需通勤，Sponsor 希望得知每条通勤路线 $x_i$ 到 $y_i$ 在补图上的最优路径权值。

但是 Sponsor 只是一个市长，他希望你能求出这些数

输入格式

第一行两个正整数 $n, m$，表示地点数和道路数。

接下来 $m$ 行，第 $i + 1$ 行有三个正整数 $x_i\ ,\ y_i\ ,\ z_i\ (1 \leq x_i, y_i \leq n, 1 \leq z_i \leq 10^9)$，表示一条通勤路线。$x_i$ 和 $y_i$ 之间有一条权值 $z_i$ 的无向边。

输出格式

输出包含一行 $m$ 个整数，表示补图上 $x_i$ 到 $y_i$ 的最优路径权值。

样例输入

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

样例输出

4 4 5 3 4 4