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>
const long long INF = 2e9;
const long long md = 1e9 + 7;
using namespace std;
struct str {
  int u, v, e;
  bool operator<(const str& other) const {
    if (e == other.e) {
      if (u == other.u) {
        return v < other.v;
      }
      return u < other.u;
    }
    return e < other.e;
  }
};
class SegmentTree {
 private:
  void createSons() {
    if (left == nullptr) {
      left = new SegmentTree();
      left->tl = this->tl;
      left->tr = (this->tl + this->tr) / 2;
    }
    if (right == nullptr) {
      right = new SegmentTree();
      right->tl = (tl + tr) / 2 + 1;
      right->tr = tr;
    }
  }
  void doPush() {
    createSons();
    if (push == INF) {
      return;
    }
    left->push = min(left->push, push);
    right->push = min(right->push, push);
    value = min(value, push);
  }

 public:
  int value = 1e9;
  SegmentTree* left = nullptr;
  SegmentTree* right = nullptr;
  int push = INF;
  int tl = 0, tr = 1e5;
  int get(int l, int r) {
    doPush();
    if (tr < l || tl > r) {
      return 1e9;
    }
    if (l <= tl && tr <= r) {
      return value;
    }
    createSons();
    return min(left->get(l, r), right->get(l, r));
  }
  void update(int l, int r, int val) {
    doPush();
    if (tr < l || tl > r) {
      return;
    }
    if (l <= tl && tr <= r) {
      push = min(push, val);
      doPush();
      return;
    }
    createSons();
    left->update(l, r, val);
    right->update(l, r, val);
    value = min(left->value, right->value);
  }
};
int n, m;
vector<str> input;
vector<str> edges;
vector<str> treeEdges;
vector<pair<int, int>> g[100005];
map<str, bool> used;
int p[100005];
int sp[100005][22];
int spMx[100005][22];
int depth[100005];
int timer = 1;
int tIn[100005], tOut[100005];
int pred[100005];
int subTreeSize[100005];
vector<SegmentTree> segmentTree;
int dsu_get(int v) { return p[v] == v ? v : p[v] = dsu_get(p[v]); }
void dsu_unite(int a, int b) {
  a = dsu_get(a);
  b = dsu_get(b);
  if (rand() % 2) {
    p[b] = a;
  } else {
    p[a] = b;
  }
}
vector<str> khruskal() {
  vector<str> res;
  for (int i = 0; i < 1e5; i++) {
    p[i] = i;
  }
  for (auto i : edges) {
    int u = i.u;
    int v = i.v;
    if (dsu_get(u) != dsu_get(v)) {
      dsu_unite(u, v);
      res.push_back(i);
      used[i] = true;
    }
  }
  return res;
}
void dfs(int v, int pred, int w, int dpth) {
  depth[v] = dpth;
  sp[v][0] = pred;
  spMx[v][0] = w;
  for (auto i : g[v]) {
    if (i.first != pred) {
      dfs(i.first, v, i.second, dpth + 1);
    }
  }
}
int fastLog2(int a) {
  int ans = 0;
  int cur = 1;
  while (cur <= a) {
    cur *= 2;
    ans++;
  }
  return ans - 1;
}
int get_lca(int a, int b, int& s1, int& s2) {
  bool sw = false;
  if (depth[a] < depth[b]) {
    swap(a, b);
    sw = 1;
  }
  int razn = depth[a] - depth[b] - 1;
  while (razn > 0) {
    int cur = fastLog2(razn);
    a = sp[a][cur];
    razn -= 1ll << cur;
  }
  int v = a;
  while (depth[a] > depth[b]) {
    v = a;
    a = pred[a];
  }
  if (a == b) {
    s1 = v;
    s2 = v;
    return a;
  }
  while (true) {
    for (int i = 0; i < 17; i++) {
      if (sp[a][i] == sp[b][i]) {
        if (i == 0) {
          s1 = a;
          s2 = b;
          if (sw) {
            s2 = a;
            s1 = b;
          }
          return sp[a][i];
        }
        a = sp[a][i - 1];
        b = sp[b][i - 1];
        break;
      }
    }
  }
}
int get_max(int a, int b) {
  int razn = depth[a] - depth[b];
  int res = 0;
  while (razn != 0) {
    int cur = fastLog2(razn);
    res = max(spMx[a][cur], res);
    a = sp[a][cur];
    razn -= (1ll << cur);
  }
  return res;
}
void dfs(int v) {
  tIn[v] = timer++;
  subTreeSize[v] = 1;
  for (auto i : g[v]) {
    if (!tIn[i.first]) {
      pred[i.first] = v;
      dfs(i.first);
      subTreeSize[v] += subTreeSize[i.first];
    }
  }
  tOut[v] = timer++;
}
bool isPred(int a, int b) { return (tIn[a] <= tIn[b] && tOut[b] <= tOut[a]); }
int inChainPositionOfVertex[100005];
int chainNumOfVertex[100005];
int chainSize[100005];
int chainRoot[100005];
int chainsCount = 0;
void buildHLD(int v, int chainNum) {
  chainNumOfVertex[v] = chainNum;
  inChainPositionOfVertex[v] = chainSize[chainNum];
  chainSize[chainNum]++;
  if (chainSize[chainNum] == 1) {
    chainRoot[chainNum] = v;
  }
  int maxChild = -1;
  for (auto i : g[v]) {
    if (i.first != pred[v] &&
        (maxChild == -1 || subTreeSize[i.first] > subTreeSize[maxChild])) {
      maxChild = i.first;
    }
  }
  if (maxChild != -1) {
    for (auto i : g[v]) {
      if (i.first == pred[v]) {
        continue;
      }
      if (i.first == maxChild) {
        buildHLD(i.first, chainNum);
      } else {
        segmentTree.push_back({});
        buildHLD(i.first, ++chainsCount);
      }
    }
  }
}
int getHLD(int a, int b) {
  segmentTree[chainNumOfVertex[a]].tl = 0;
  segmentTree[chainNumOfVertex[a]].tr = chainSize[chainNumOfVertex[a]];
  return segmentTree[chainNumOfVertex[a]].get(inChainPositionOfVertex[a],
                                              inChainPositionOfVertex[a]);
}
void updateHLD(int a, int b, int val) {
  while (1) {
    if (isPred(chainRoot[chainNumOfVertex[a]], b)) {
      break;
    }
    segmentTree[chainNumOfVertex[a]].tl = 0;
    segmentTree[chainNumOfVertex[a]].tr = chainSize[chainNumOfVertex[a]];
    segmentTree[chainNumOfVertex[a]].update(0, inChainPositionOfVertex[a], val);
    a = pred[chainRoot[chainNumOfVertex[a]]];
  }
  if (inChainPositionOfVertex[a] > inChainPositionOfVertex[b]) {
    swap(a, b);
  }
  segmentTree[chainNumOfVertex[a]].tl = 0;
  segmentTree[chainNumOfVertex[a]].tr = chainSize[chainNumOfVertex[a]];
  segmentTree[chainNumOfVertex[a]].update(inChainPositionOfVertex[a],
                                          inChainPositionOfVertex[b], val);
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, e;
    cin >> u >> v >> e;
    input.push_back({u, v, e});
  }
  edges = input;
  sort(edges.begin(), edges.end());
  treeEdges = khruskal();
  for (auto& i : treeEdges) {
    g[i.v].push_back({i.u, i.e});
    g[i.u].push_back({i.v, i.e});
  }
  dfs(1, 0, 0, 1);
  for (int step = 1; step < 17; step++) {
    for (int i = 1; i <= n; i++) {
      sp[i][step] = sp[sp[i][step - 1]][step - 1];
      spMx[i][step] = max(spMx[i][step - 1], spMx[sp[i][step - 1]][step - 1]);
    }
  }
  vector<int> ans;
  dfs(1);
  segmentTree.push_back({});
  segmentTree.push_back({});
  buildHLD(1, ++chainsCount);
  for (auto& i : input) {
    if (used[i]) {
      continue;
    }
    int a = i.v, b = i.u;
    int s1Lca = a, s2Lca = b;
    int lca = get_lca(a, b, s1Lca, s2Lca);
    int mx1 = get_max(a, lca);
    int mx2 = get_max(b, lca);
    ans.push_back(max(mx1, mx2));
    if (a != lca) {
      updateHLD(a, s1Lca, i.e);
    }
    if (b != lca) {
      updateHLD(b, s2Lca, i.e);
    }
  }
  auto it = ans.begin();
  for (auto& i : input) {
    if (used[i]) {
      int a;
      if (pred[i.u] == i.v) {
        a = i.u;
      } else {
        a = i.v;
      }
      int res = getHLD(a, a);
      cout << res << '\n';
      continue;
    } else {
      cout << *it << '\n';
      it++;
    }
  }
}
