#include <bits/stdc++.h>
int RD() {
  char cr;
  int res;
  while ((cr = getchar()) < '0' || cr > '9')
    ;
  res = cr - '0';
  while ((cr = getchar()) >= '0' && cr <= '9') res = res * 10 + cr - '0';
  return res;
}
int segtree_sc[400005];
int e[400005 * 2], nxt[400005 * 2], wi[400005 * 2], head[400005], egtot;
int fa[400005], fson[400005], maxsonnum[400005], num[400005];
int ltop[400005], hei[400005];
int val[400005], ptr[400005];
int q[400005];
int wf[400005], qf[19][400005], qw[19][400005];
int n;
int tmin[600050];
void setsegtree(int l, int r, int p) {
  tmin[p] = 1000000007;
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  setsegtree(l, mid, p * 2);
  setsegtree(mid + 1, r, p * 2 + 1);
}
void modify(int l, int r, int p, int gl, int gr, int gv) {
  if (l == gl && r == gr) {
    tmin[p] = (tmin[p] < gv ? tmin[p] : gv);
    return;
  }
  int mid = (l + r) / 2;
  if (gr <= mid)
    modify(l, mid, p * 2, gl, gr, gv);
  else if (gl > mid)
    return modify(mid + 1, r, p * 2 + 1, gl, gr, gv);
  else
    modify(l, mid, p * 2, gl, mid, gv),
        modify(mid + 1, r, p * 2 + 1, mid + 1, gr, gv);
}
int querymin(int l, int r, int p, int gp) {
  if (l == gp && r == gp) return tmin[p];
  int mid = (l + r) / 2;
  int ans = tmin[p], res;
  if (gp <= mid)
    res = querymin(l, mid, p * 2, gp);
  else
    res = querymin(mid + 1, r, p * 2 + 1, gp);
  return (ans < res ? ans : res);
}
void addEdge(int p1, int p2, int w) {
  e[++egtot] = p2;
  wi[egtot] = w;
  nxt[egtot] = head[p1];
  head[p1] = egtot;
}
void setTree() {
  int l = 1, r = 1;
  q[l] = 1;
  hei[1] = 1;
  while (l <= r) {
    int p = q[l++];
    for (int i = head[p]; i; i = nxt[i])
      if (e[i] != fa[p]) {
        fa[e[i]] = p;
        wf[e[i]] = wi[i];
        q[++r] = e[i];
        hei[e[i]] = hei[p] + 1;
      }
  }
  for (int i = n, p; i >= 1; i--) {
    p = q[i];
    ltop[p] = p;
    num[p]++;
    num[fa[p]] += num[p];
    if (num[p] > maxsonnum[fa[p]]) {
      ltop[fson[fa[p]]] = fson[fa[p]];
      ltop[p] = fa[p];
      fson[fa[p]] = p;
      maxsonnum[fa[p]] = num[p];
    }
  }
  ltop[1] = 1;
  for (int i = 1; i <= n; i++) ltop[q[i]] = ltop[ltop[q[i]]];
  int cnt = 0;
  l = 1;
  r = 1;
  q[1] = 1;
  while (l <= r) {
    int p = q[l++];
    while (p != 0) {
      segtree_sc[++cnt] = val[p];
      ptr[p] = cnt;
      for (int i = head[p]; i; i = nxt[i])
        if (e[i] != fa[p] && e[i] != fson[p]) q[++r] = e[i];
      p = fson[p];
    }
  }
}
void work(int p1, int p2, int w) {
  while (ltop[p1] != ltop[p2]) {
    if (hei[ltop[p1]] < hei[ltop[p2]]) {
      int __temp;
      __temp = p1;
      p1 = p2;
      p2 = __temp;
    };
    modify(1, n, 1, ptr[ltop[p1]], ptr[p1], w);
    p1 = fa[ltop[p1]];
  }
  if (hei[p1] < hei[p2]) {
    int __temp;
    __temp = p1;
    p1 = p2;
    p2 = __temp;
  };
  if (p1 != p2) modify(1, n, 1, ptr[p2] + 1, ptr[p1], w);
}
struct Edge {
  int p1, p2, w, id, ans;
} eg[400005];
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int used[400005];
int dset[400005];
int find(int p) { return dset[p] == p ? p : dset[p] = find(dset[p]); }
int solve(int p1, int p2) {
  if (hei[p1] < hei[p2]) {
    int __temp;
    __temp = p1;
    p1 = p2;
    p2 = __temp;
  };
  int ans = 0;
  int delta = hei[p1] - hei[p2];
  for (int i = 18; i >= 0; i--)
    if ((delta >> i) & 1) {
      ans = (ans > qw[i][p1] ? ans : qw[i][p1]);
      p1 = qf[i][p1];
    }
  if (p1 == p2) return ans;
  for (int i = 18; i >= 0; i--) {
    if (qf[i][p1] != qf[i][p2]) {
      ans = (ans > qw[i][p1] ? ans : qw[i][p1]);
      ans = (ans > qw[i][p2] ? ans : qw[i][p2]);
      p1 = qf[i][p1];
      p2 = qf[i][p2];
    }
  }
  ans = (ans > qw[0][p1] ? ans : qw[0][p1]);
  ans = (ans > qw[0][p2] ? ans : qw[0][p2]);
  return ans;
}
int raa[400005];
int main() {
  int m;
  n = RD();
  m = RD();
  for (int i = 1; i <= m; i++) {
    eg[i].p1 = RD();
    eg[i].p2 = RD();
    eg[i].w = RD();
    eg[i].id = i;
  }
  std::sort(eg + 1, eg + 1 + m, cmp);
  for (int i = 1; i <= n; i++) dset[i] = i;
  for (int i = 1; i <= m; i++) {
    Edge &e = eg[i];
    int f1 = find(e.p1), f2 = find(e.p2);
    if (f1 != f2) {
      dset[f1] = f2;
      used[i] = 1;
      addEdge(e.p1, e.p2, e.w);
      addEdge(e.p2, e.p1, e.w);
    }
  }
  setTree();
  for (int i = 1; i <= n; i++) qf[0][i] = fa[i], qw[0][i] = wf[i];
  for (int i = 1; i <= 18; i++)
    for (int p = 1; p <= n; p++) {
      qf[i][p] = qf[i - 1][qf[i - 1][p]];
      qw[i][p] =
          (qw[i - 1][p] > qw[i - 1][qf[i - 1][p]] ? qw[i - 1][p]
                                                  : qw[i - 1][qf[i - 1][p]]);
    }
  setsegtree(1, n, 1);
  for (int i = 1; i <= m; i++)
    if (!used[i]) {
      eg[i].ans = solve(eg[i].p1, eg[i].p2) - 1;
      work(eg[i].p1, eg[i].p2, eg[i].w);
    }
  for (int i = 1; i <= m; i++)
    if (used[i]) {
      int p = fa[eg[i].p1] == eg[i].p2 ? eg[i].p1 : eg[i].p2;
      eg[i].ans = querymin(1, n, 1, ptr[p]) - 1;
    }
  for (int i = 1; i <= m; i++) raa[eg[i].id] = eg[i].ans;
  for (int i = 1; i <= m; i++)
    printf("%d%c", raa[i] < 1000000007 - 5 ? raa[i] : -1, i < m ? ' ' : '\n');
}

### Prompt

In CPP, your task is to solve the following problem:

You are given a connected weighted graph with n vertices and m edges. The graph doesn't contain loops nor multiple edges. Consider some edge with id i. Let's determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don't change the other weights.

You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can't be two edges with changed weights at the same time.

Input

The first line contains two integers n and m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105), where n and m are the number of vertices and the number of edges in the graph, respectively.

Each of the next m lines contains three integers u, v and c (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ c ≤ 109) meaning that there is an edge between vertices u and v with weight c. 

Output

Print the answer for each edge in the order the edges are given in the input. If an edge is contained in every minimum spanning tree with any weight, print -1 as the answer.

Examples

Input

4 4
1 2 2
2 3 2
3 4 2
4 1 3


Output

2 2 2 1 

Input

4 3
1 2 2
2 3 2
3 4 2


Output

-1 -1 -1 

### Response

```cpp
#include <bits/stdc++.h>
int RD() {
  char cr;
  int res;
  while ((cr = getchar()) < '0' || cr > '9')
    ;
  res = cr - '0';
  while ((cr = getchar()) >= '0' && cr <= '9') res = res * 10 + cr - '0';
  return res;
}
int segtree_sc[400005];
int e[400005 * 2], nxt[400005 * 2], wi[400005 * 2], head[400005], egtot;
int fa[400005], fson[400005], maxsonnum[400005], num[400005];
int ltop[400005], hei[400005];
int val[400005], ptr[400005];
int q[400005];
int wf[400005], qf[19][400005], qw[19][400005];
int n;
int tmin[600050];
void setsegtree(int l, int r, int p) {
  tmin[p] = 1000000007;
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  setsegtree(l, mid, p * 2);
  setsegtree(mid + 1, r, p * 2 + 1);
}
void modify(int l, int r, int p, int gl, int gr, int gv) {
  if (l == gl && r == gr) {
    tmin[p] = (tmin[p] < gv ? tmin[p] : gv);
    return;
  }
  int mid = (l + r) / 2;
  if (gr <= mid)
    modify(l, mid, p * 2, gl, gr, gv);
  else if (gl > mid)
    return modify(mid + 1, r, p * 2 + 1, gl, gr, gv);
  else
    modify(l, mid, p * 2, gl, mid, gv),
        modify(mid + 1, r, p * 2 + 1, mid + 1, gr, gv);
}
int querymin(int l, int r, int p, int gp) {
  if (l == gp && r == gp) return tmin[p];
  int mid = (l + r) / 2;
  int ans = tmin[p], res;
  if (gp <= mid)
    res = querymin(l, mid, p * 2, gp);
  else
    res = querymin(mid + 1, r, p * 2 + 1, gp);
  return (ans < res ? ans : res);
}
void addEdge(int p1, int p2, int w) {
  e[++egtot] = p2;
  wi[egtot] = w;
  nxt[egtot] = head[p1];
  head[p1] = egtot;
}
void setTree() {
  int l = 1, r = 1;
  q[l] = 1;
  hei[1] = 1;
  while (l <= r) {
    int p = q[l++];
    for (int i = head[p]; i; i = nxt[i])
      if (e[i] != fa[p]) {
        fa[e[i]] = p;
        wf[e[i]] = wi[i];
        q[++r] = e[i];
        hei[e[i]] = hei[p] + 1;
      }
  }
  for (int i = n, p; i >= 1; i--) {
    p = q[i];
    ltop[p] = p;
    num[p]++;
    num[fa[p]] += num[p];
    if (num[p] > maxsonnum[fa[p]]) {
      ltop[fson[fa[p]]] = fson[fa[p]];
      ltop[p] = fa[p];
      fson[fa[p]] = p;
      maxsonnum[fa[p]] = num[p];
    }
  }
  ltop[1] = 1;
  for (int i = 1; i <= n; i++) ltop[q[i]] = ltop[ltop[q[i]]];
  int cnt = 0;
  l = 1;
  r = 1;
  q[1] = 1;
  while (l <= r) {
    int p = q[l++];
    while (p != 0) {
      segtree_sc[++cnt] = val[p];
      ptr[p] = cnt;
      for (int i = head[p]; i; i = nxt[i])
        if (e[i] != fa[p] && e[i] != fson[p]) q[++r] = e[i];
      p = fson[p];
    }
  }
}
void work(int p1, int p2, int w) {
  while (ltop[p1] != ltop[p2]) {
    if (hei[ltop[p1]] < hei[ltop[p2]]) {
      int __temp;
      __temp = p1;
      p1 = p2;
      p2 = __temp;
    };
    modify(1, n, 1, ptr[ltop[p1]], ptr[p1], w);
    p1 = fa[ltop[p1]];
  }
  if (hei[p1] < hei[p2]) {
    int __temp;
    __temp = p1;
    p1 = p2;
    p2 = __temp;
  };
  if (p1 != p2) modify(1, n, 1, ptr[p2] + 1, ptr[p1], w);
}
struct Edge {
  int p1, p2, w, id, ans;
} eg[400005];
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int used[400005];
int dset[400005];
int find(int p) { return dset[p] == p ? p : dset[p] = find(dset[p]); }
int solve(int p1, int p2) {
  if (hei[p1] < hei[p2]) {
    int __temp;
    __temp = p1;
    p1 = p2;
    p2 = __temp;
  };
  int ans = 0;
  int delta = hei[p1] - hei[p2];
  for (int i = 18; i >= 0; i--)
    if ((delta >> i) & 1) {
      ans = (ans > qw[i][p1] ? ans : qw[i][p1]);
      p1 = qf[i][p1];
    }
  if (p1 == p2) return ans;
  for (int i = 18; i >= 0; i--) {
    if (qf[i][p1] != qf[i][p2]) {
      ans = (ans > qw[i][p1] ? ans : qw[i][p1]);
      ans = (ans > qw[i][p2] ? ans : qw[i][p2]);
      p1 = qf[i][p1];
      p2 = qf[i][p2];
    }
  }
  ans = (ans > qw[0][p1] ? ans : qw[0][p1]);
  ans = (ans > qw[0][p2] ? ans : qw[0][p2]);
  return ans;
}
int raa[400005];
int main() {
  int m;
  n = RD();
  m = RD();
  for (int i = 1; i <= m; i++) {
    eg[i].p1 = RD();
    eg[i].p2 = RD();
    eg[i].w = RD();
    eg[i].id = i;
  }
  std::sort(eg + 1, eg + 1 + m, cmp);
  for (int i = 1; i <= n; i++) dset[i] = i;
  for (int i = 1; i <= m; i++) {
    Edge &e = eg[i];
    int f1 = find(e.p1), f2 = find(e.p2);
    if (f1 != f2) {
      dset[f1] = f2;
      used[i] = 1;
      addEdge(e.p1, e.p2, e.w);
      addEdge(e.p2, e.p1, e.w);
    }
  }
  setTree();
  for (int i = 1; i <= n; i++) qf[0][i] = fa[i], qw[0][i] = wf[i];
  for (int i = 1; i <= 18; i++)
    for (int p = 1; p <= n; p++) {
      qf[i][p] = qf[i - 1][qf[i - 1][p]];
      qw[i][p] =
          (qw[i - 1][p] > qw[i - 1][qf[i - 1][p]] ? qw[i - 1][p]
                                                  : qw[i - 1][qf[i - 1][p]]);
    }
  setsegtree(1, n, 1);
  for (int i = 1; i <= m; i++)
    if (!used[i]) {
      eg[i].ans = solve(eg[i].p1, eg[i].p2) - 1;
      work(eg[i].p1, eg[i].p2, eg[i].w);
    }
  for (int i = 1; i <= m; i++)
    if (used[i]) {
      int p = fa[eg[i].p1] == eg[i].p2 ? eg[i].p1 : eg[i].p2;
      eg[i].ans = querymin(1, n, 1, ptr[p]) - 1;
    }
  for (int i = 1; i <= m; i++) raa[eg[i].id] = eg[i].ans;
  for (int i = 1; i <= m; i++)
    printf("%d%c", raa[i] < 1000000007 - 5 ? raa[i] : -1, i < m ? ' ' : '\n');
}

```