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;
class UnionFind {
 private:
  vector<int> p, r;

 public:
  UnionFind(int n) {
    r.assign(n, 0);
    p.assign(n, 0);
    iota(begin(p), end(p), 0);
  }
  int findset(int i) { return (p[i] == i) ? i : (p[i] = findset(p[i])); }
  bool unionset(int i, int j) {
    int x = findset(i), y = findset(j);
    if (x != y) {
      if (r[x] > r[y])
        p[y] = x;
      else {
        p[x] = y;
        if (r[x] == r[y]) ++r[y];
      }
      return true;
    } else
      return false;
  }
};
struct edge {
  int A, B, E, I;
  edge(int a, int b, int e, int i) : A(a), B(b), E(e), I(i){};
};
const int MAXN = 1e5 + 5;
const int lgN = 17;
const int MAXM = 1e6 + 5;
int N, M;
vector<pair<int, int> > al[MAXN];
vector<edge> el;
bool mst[MAXM];
int ans[MAXM];
struct node {
  int s, e, m, vmin, vmax;
  node *l, *r;
  node(int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), vmin(1e9), vmax(0) {
    if (s != e) l = new node(s, m), r = new node(m + 1, e);
  }
  void urmin(int x, int y, int z) {
    if (s == x and e == y)
      vmin = min(vmin, z);
    else if (y <= m)
      l->urmin(x, y, z);
    else if (x > m)
      r->urmin(x, y, z);
    else
      l->urmin(x, m, z), r->urmin(m + 1, y, z);
  }
  int qpmin(int x) {
    if (s == e)
      return vmin;
    else if (x <= m)
      return min(vmin, l->qpmin(x));
    else
      return min(vmin, r->qpmin(x));
  }
} * root;
int pa[MAXN][lgN], dst[MAXN][lgN], dep[MAXN];
int heavy[MAXN], head[MAXN], pos[MAXN], ptr;
int dfs(int u, int p, int d) {
  pa[u][0] = p;
  for (int k = 1; k <= lgN - 1; ++k) {
    pa[u][k] = (pa[u][k - 1] == -1 ? -1 : pa[pa[u][k - 1]][k - 1]);
    dst[u][k] =
        (pa[u][k - 1] == -1 ? 0 : max(dst[u][k - 1], dst[pa[u][k - 1]][k - 1]));
  }
  dep[u] = d, heavy[u] = -1;
  int sz = 1, mchild = 0;
  for (auto v : al[u])
    if (v.first != p) {
      dst[v.first][0] = v.second;
      int cs = dfs(v.first, u, d + 1);
      sz += cs;
      if (cs > mchild) mchild = v.first, heavy[u] = v.first;
    }
  return sz;
}
void decompose(int u, int p, int h) {
  head[u] = h;
  pos[u] = ptr++;
  if (heavy[u] != -1) decompose(heavy[u], u, h);
  for (auto v : al[u])
    if (v.first != p and v.first != heavy[u]) decompose(v.first, u, v.first);
}
void init(int rt) {
  dfs(rt, 0, 0);
  ptr = 0;
  decompose(rt, 0, 0);
  root = new node(0, ptr - 1);
}
void update_path_min(int a, int b, int c) {
  for (; head[a] != head[b]; a = pa[head[a]][0]) {
    if (dep[head[a]] < dep[head[b]]) swap(a, b);
    root->urmin(pos[head[a]], pos[a], c);
  }
  if (a == b) return;
  if (dep[a] < dep[b]) swap(a, b);
  root->urmin(pos[b] + 1, pos[a], c);
}
int query_path_max(int a, int b) {
  int ans = 0;
  if (dep[a] < dep[b]) swap(a, b);
  for (int k = lgN - 1; k >= 0; --k)
    if (pa[a][k] != -1 and dep[pa[a][k]] >= dep[b])
      ans = max(ans, dst[a][k]), a = pa[a][k];
  if (a == b) return ans;
  for (int k = lgN - 1; k >= 0; --k)
    if (pa[a][k] != -1 and pa[b][k] != -1 and pa[a][k] != pa[b][k])
      ans = max({ans, dst[a][k], dst[b][k]}), a = pa[a][k], b = pa[b][k];
  return ans = max({ans, dst[a][0], dst[b][0]});
}
int query_edge_min(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  return root->qpmin(pos[a]);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  for (int i = 0; i <= M - 1; ++i) {
    int A, B, E;
    cin >> A >> B >> E;
    el.emplace_back(A, B, E, i);
  }
  sort(begin(el), end(el), [](edge a, edge b) { return a.E < b.E; });
  UnionFind UF(N + 1);
  for (auto e : el)
    if (UF.unionset(e.A, e.B)) {
      mst[e.I] = 1;
      al[e.A].emplace_back(e.B, e.E);
      al[e.B].emplace_back(e.A, e.E);
    }
  init(1);
  for (auto e : el)
    if (!mst[e.I]) {
      ans[e.I] = query_path_max(e.A, e.B);
      update_path_min(e.A, e.B, e.E);
    }
  for (auto e : el)
    if (mst[e.I]) {
      ans[e.I] = query_edge_min(e.A, e.B);
    }
  for (int i = 0; i <= M - 1; ++i) cout << ans[i] << '\n';
}
