func_code_string: #include <bits/stdc++.h>   using namespace std;   const int INF = 1e9 + 239;   int n;   vector<vector<int>> g;   vector<vector<pair<int, int>>> g2;   namespace Lca {   const int LIM = 20;   int timer = 0;   vector<int> tin;   vector<int> tout;   vector<int> p;   vector<int> c;   vector<int> h;   vector<vector<int>> uc;   vector<vector<int>> up;   void dfs(int cur, int pr, int cs, int ch) {     c[cur] = cs;     p[cur] = pr;     h[cur] = ch;     tin[cur] = timer;     timer++;     for (auto [t, w] : g2[cur]) {       if (t != pr) {         dfs(t, cur, w, ch + 1);       }     }     tout[cur] = timer;     timer++;   }   bool parent(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }   void calc_up() {     up.resize(LIM, vector<int>(n));     uc.resize(LIM, vector<int>(n));     for (int i = 0; i < n; i++) {       up[0][i] = p[i];       uc[0][i] = c[i];     }     for (int i = 0; i + 1 < LIM; i++) {       for (int j = 0; j < n; j++) {         int mid = up[i][j];         if (mid != -1) {           up[i + 1][j] = up[i][mid];           uc[i + 1][j] = max(uc[i][mid], uc[i][j]);         }       }     }   }   int get(int a, int b) {     if (parent(a, b)) {       return a;     } else if (parent(b, a)) {       return b;     } else {       int cur = a;       for (int i = LIM - 1; i >= 0; i--) {         if (up[i][cur] != -1 && !parent(up[i][cur], b)) {           cur = up[i][cur];         }       }       return p[cur];     }   }   int get_up(int a, int h) {     int ans = -INF;     for (int i = 0; i < LIM; i++) {       if ((h >> i) & 1) {         ans = max(ans, uc[i][a]);         a = up[i][a];       }     }     return ans;   }   int get_cost(int a, int b) {     auto l = get(a, b);     return max(get_up(a, h[a] - h[l]), get_up(b, h[b] - h[l]));   }   void init() {     tin.resize(n);     tout.resize(n);     p.resize(n, -1);     c.resize(n, -1);     h.resize(n, -1);     dfs(0, -1, 0, 0);     calc_up();   }   }  // namespace Lca   namespace Dsu {   vector<int> p;   vector<int> rank;   int get(int v) {     if (p[v] != v) {       p[v] = get(p[v]);     }     return p[v];   }   void merge(int a, int b) {     a = get(a);     b = get(b);     if (a != b) {       if (rank[a] < rank[b]) {         swap(a, b);       }       p[b] = a;       if (rank[a] == rank[b]) {         rank[a]++;       }     }   }   void init() {     p.resize(n);     for (int i = 0; i < n; i++) {       p[i] = i;     }     rank.resize(n);   }   }  // namespace Dsu   struct SegmentTree {     vector<int> a;     vector<vector<int>> st;     vector<vector<int>> en;     void modify(int l, int r, int val) {       st[l].push_back(val);       en[r].push_back(val);     }     void solve() {       multiset<int> cur;       cur.insert(INF);       for (int i = 0; i < (int)a.size(); i++) {         for (auto t : st[i]) {           cur.insert(t);         }         for (auto t : en[i]) {           cur.erase(cur.find(t));         }         a[i] = *(cur.begin());       }     }     int get(int pos) { return a[pos]; }     SegmentTree(vector<int> &a_) {       a = a_;       for (auto &t : a) {         t = INF;       }       st.resize(a.size());       en.resize(a.size() + 1);     }   };   namespace Hld {   vector<int> p;   vector<int> h;   vector<int> sz;   vector<int> where;   vector<int> pos_in_list;   vector<vector<int>> lists;   vector<SegmentTree> lists_st;   int cur_cnt = 1;   void dfs(int cur, int pr, int ch) {     sz[cur] = 1;     h[cur] = ch;     for (auto t : g[cur]) {       if (t != pr) {         dfs(t, cur, ch + 1);         sz[cur] += sz[t];       }     }   }   void build(int v, int wh, int pr) {     p[v] = pr;     where[v] = wh;     pos_in_list[v] = (int)lists[wh].size();     lists[wh].push_back(v);     int mx = -1;     for (auto t : g[v]) {       if (t == pr) {         continue;       }       if (2 * sz[t] > sz[v]) {         assert(mx == -1);         mx = t;       }     }     if (mx != -1) {       build(mx, wh, v);     }     for (auto t : g[v]) {       if (t == pr || t == mx) {         continue;       }       {         lists.push_back(vector<int>());         build(t, cur_cnt, v);         cur_cnt++;       }     }   }   void init_st() {     for (auto t : lists) {       lists_st.push_back(SegmentTree(t));     }   }   void mod_up(int v, int to, int val) {     while (to > 0) {       int i = where[v];       int j = pos_in_list[v];       int can = min(to, j + 1);       int l = (j + 1) - can;       int r = j + 1;       lists_st[i].modify(l, r, val);       to -= can;       v = p[lists[i].front()];     }   }   void mod(int u, int v, int val) {     int l = Lca::get(u, v);     mod_up(u, h[u] - h[l], val);     mod_up(v, h[v] - h[l], val);   }   void solve() {     for (int i = 0; i < (int)lists_st.size(); i++) {       lists_st[i].solve();     }   }   void init() {     p.resize(n);     h.resize(n);     sz.resize(n);     where.resize(n);     pos_in_list.resize(n);     lists.push_back(vector<int>());     dfs(0, -1, 0);     build(0, 0, -1);     init_st();   }   int get(int v) {     int i = where[v];     int j = pos_in_list[v];     return lists_st[i].get(j);   }   };  // namespace Hld   struct Edge {     int u, v, c;     Edge() {}   };   vector<int> in;   vector<Edge> ed;   void Kr() {     auto cmp = [&](int a, int b) { return ed[a].c < ed[b].c; };     vector<int> ind((int)ed.size());     for (int i = 0; i < (int)ed.size(); i++) {       ind[i] = i;     }     sort(ind.begin(), ind.end(), cmp);     Dsu::init();     for (int i = 0; i < (int)ed.size(); i++) {       Edge t = ed[ind[i]];       int f = Dsu::get(t.u);       int s = Dsu::get(t.v);       if (f != s) {         in[ind[i]] = 1;         g[t.u].push_back(t.v);         g[t.v].push_back(t.u);         g2[t.u].push_back({t.v, t.c});         g2[t.v].push_back({t.u, t.c});         Dsu::merge(f, s);       }     }   }   signed main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     int m;     cin >> n >> m;     g.resize(n);     g2.resize(n);     in.resize(m);     ed.resize(m);     for (auto &t : ed) {       cin >> t.u >> t.v >> t.c;       t.u--;       t.v--;     }     Kr();     cerr <<  Kr ok  << endl;     Lca::init();     cerr <<  Lca ok  << endl;     Hld::init();     cerr <<  Hld ok  << endl;     for (auto &t : ed) {       if (Hld::h[t.u] > Hld::h[t.v]) {         swap(t.u, t.v);       }     }     vector<int> ans(m, -1);     for (int i = 0; i < m; i++) {       if (!in[i]) {         ans[i] = Lca::get_cost(ed[i].u, ed[i].v) - 1;       }     }     cerr <<  st md  << endl;     for (int i = 0; i < m; i++) {       if (!in[i]) {         Hld::mod(ed[i].u, ed[i].v, ed[i].c);       }     }     cerr <<  slv   << endl;     Hld::solve();     cerr <<  st qr  << endl;     for (int i = 0; i < m; i++) {       if (in[i]) {         ans[i] = Hld::get(ed[i].v) - 1;         if (ans[i] == INF - 1) {           ans[i] = -1;         }       }     }     for (auto t : ans) {       cout << t <<    ;     }     cout << endl;   }   