With your help, Heidi has prepared a plan of trap placement and defence. Yet suddenly, the Doctor popped out of the TARDIS and told her that he had spied on the Daleks' preparations, and there is more of them than ever. Desperate times require desperate measures, so Heidi is going to risk meeting with the Daleks and she will consider placing a trap along any Corridor.

This means she needs your help again in calculating E_{max}(c) – the largest e ≤ 10^9 such that if we changed the energy requirement of c to e, then the Daleks might use c in their invasion – but this time for all Time Corridors.

Input

First line: number n of destinations, number m of corridors (2 ≤ n ≤ 10^5, n - 1 ≤ m ≤ 10^6). The next m lines: destinations a, b and energy e (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ e ≤ 10^9).

No pair \\{a, b\} will repeat. The graph is guaranteed to be connected. It is not guaranteed that all energy requirements e are distinct, or that the minimum spanning tree is unique.

Output

Output m lines, each containing one integer: E_{max}(c_i) for the i-th Corridor c_i from the input.

Example

Input

3 3
1 2 8
2 3 3
3 1 4


Output

4
8
8
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... r) {
  read(x);
  read(r...);
}
const int maxn = 2e5 + 10;
const int maxm = 2e6 + 10;
const int maxe = 1e9;
struct edge_t {
  int nxt;
  int u;
  int v;
  int w;
  bool t;
};
int tot;
int head[maxn];
edge_t edge[maxm];
inline void init_edge() {
  tot = 0;
  memset(head, -1, sizeof head);
}
inline void add_edge(int u, int v, int w, bool b = false) {
  edge[++tot] = {head[u], u, v, w, b};
  head[u] = tot;
}
int dds[maxn];
inline void init_dds(int n) {
  for (int i = 1; i <= n; i++) dds[i] = i;
}
int dds_find(int x) {
  if (dds[x] != x) dds[x] = dds_find(dds[x]);
  return dds[x];
}
struct ew_t {
  int w;
  int id;
  bool operator<(const ew_t& r) const { return w < r.w; }
};
ew_t ew[maxm];
inline void kruskal() {
  int cnt = tot;
  for (int i = 1; i <= cnt; i++) ew[i] = {edge[i].w, i};
  sort(ew + 1, ew + 1 + cnt);
  init_dds(maxn - 1);
  for (int i = 1; i <= cnt; i++) {
    edge_t e = edge[ew[i].id];
    if (dds_find(e.u) != dds_find(e.v)) {
      edge[ew[i].id].t = true;
      dds[dds_find(e.u)] = dds_find(e.v);
      add_edge(e.v, e.u, e.w, true);
    }
  }
}
int cnt;
int fa[maxn];
int dep[maxn];
int siz[maxn];
int son[maxn];
int rk[maxn];
int top[maxn];
int id[maxn];
inline void init_tree() { cnt = 0; }
void dfs_ss(int u) {
  int ms = -1;
  int mss = 0;
  siz[u] = 1;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    if (edge[i].t) {
      int v = edge[i].v;
      if (fa[u] == v) continue;
      fa[v] = u;
      dep[v] = dep[u] + 1;
      dfs_ss(v);
      if (mss < siz[v]) {
        mss = siz[v];
        ms = v;
      }
      siz[u] += siz[v];
    }
  }
  son[u] = ms;
}
void dfs_rti(int u, int t) {
  top[u] = t;
  id[u] = ++cnt;
  rk[id[u]] = u;
  if (!~son[u]) return;
  dfs_rti(son[u], t);
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    if (edge[i].t) {
      int v = edge[i].v;
      if (son[u] != v && fa[u] != v) dfs_rti(v, v);
    }
  }
}
int tmin[maxn * 2];
int tmax[maxn * 2];
int lz[maxn * 2];
inline int ls(int x) { return x << 1; }
inline int rs(int x) { return x << 1 | 1; }
inline void push_up(int rt) {
  tmin[rt] = min(tmin[ls(rt)], tmin[rs(rt)]);
  tmax[rt] = max(tmax[ls(rt)], tmax[rs(rt)]);
}
inline void push_down(int rt) {
  lz[ls(rt)] = min(lz[ls(rt)], lz[rt]);
  lz[rs(rt)] = min(lz[rs(rt)], lz[rt]);
  tmin[ls(rt)] = min(tmin[ls(rt)], lz[rt]);
  tmin[rs(rt)] = min(tmin[rs(rt)], lz[rt]);
}
void build(int rt, int l, int r, int arr[]) {
  lz[rt] = maxe;
  if (l == r) {
    tmin[rt] = maxe;
    tmax[rt] = arr[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(ls(rt), l, mid, arr);
  build(rs(rt), mid + 1, r, arr);
  push_up(rt);
}
void upd(int rt, int l, int r, int tl, int tr, int k) {
  if (l >= tl && r <= tr) {
    tmin[rt] = min(tmin[rt], k);
    lz[rt] = min(lz[rt], k);
    return;
  }
  push_down(rt);
  int mid = (l + r) >> 1;
  if (tl <= mid) upd(ls(rt), l, mid, tl, tr, k);
  if (tr > mid) upd(rs(rt), mid + 1, r, tl, tr, k);
  push_up(rt);
}
int ask_min(int rt, int l, int r, int tl, int tr) {
  if (l == tl && r == tr) return tmin[rt];
  push_down(rt);
  int mid = (l + r) >> 1;
  if (tr <= mid) return ask_min(ls(rt), l, mid, tl, tr);
  if (tl > mid) return ask_min(rs(rt), mid + 1, r, tl, tr);
  return min(ask_min(ls(rt), l, mid, tl, mid),
             ask_min(rs(rt), mid + 1, r, mid + 1, tr));
}
int ask_max(int rt, int l, int r, int tl, int tr) {
  if (l == tl && r == tr) return tmax[rt];
  int mid = (l + r) >> 1;
  if (tr <= mid) return ask_max(ls(rt), l, mid, tl, tr);
  if (tl > mid) return ask_max(rs(rt), mid + 1, r, tl, tr);
  return max(ask_max(ls(rt), l, mid, tl, mid),
             ask_max(rs(rt), mid + 1, r, mid + 1, tr));
}
inline void tree_upd(int n, int x, int y, int k) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    upd(1, 1, n, id[top[x]], id[x], k);
    x = fa[top[x]];
  }
  if (x == y) return;
  if (dep[x] > dep[y]) swap(x, y);
  upd(1, 1, n, id[son[x]], id[y], k);
}
inline int tree_min(int n, int x, int y) {
  int res = maxe;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    res = min(res, ask_min(1, 1, n, id[top[x]], id[x]));
    x = fa[top[x]];
  }
  if (x == y) return res;
  if (dep[x] > dep[y]) swap(x, y);
  res = min(res, ask_min(1, 1, n, id[son[x]], id[y]));
  return res;
}
inline int tree_max(int n, int x, int y) {
  int res = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    res = max(res, ask_max(1, 1, n, id[top[x]], id[x]));
    x = fa[top[x]];
  }
  if (x == y) return res;
  if (dep[x] > dep[y]) swap(x, y);
  res = max(res, ask_max(1, 1, n, id[son[x]], id[y]));
  return res;
}
int arr[maxn];
int main() {
  int n, m;
  read(n, m);
  init_edge();
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    read(u, v, w);
    add_edge(u, v, w);
  }
  kruskal();
  init_tree();
  dfs_ss(1);
  dfs_rti(1, 1);
  for (int i = 1; i <= m; i++)
    if (edge[i].t)
      arr[id[dep[edge[i].u] > dep[edge[i].v] ? edge[i].u : edge[i].v]] =
          edge[i].w;
  build(1, 1, n, arr);
  for (int i = 1; i <= m; i++)
    if (!edge[i].t) tree_upd(n, edge[i].u, edge[i].v, edge[i].w);
  for (int i = 1; i <= m; i++) {
    if (edge[i].t) {
      printf("%d\n", tree_min(n, edge[i].v, edge[i].u));
    } else {
      printf("%d\n", tree_max(n, edge[i].v, edge[i].u));
    }
  }
  return 0;
}
