题意：

给定一个点数为 n，边数为 m，权值不超过 \(10^9\) 的带权连通图，没有自环与重边。 现在要求对于每一条边求出，这条边的边权最大为多少时，它还能出现在所有可能的最小生成树上，如果对于任意边权都出现，则输出 \(-1\)。

这里写一个用倍增的\(O(nlogn)\)做法。

先求出一个最小生成树。

1、若x到y在树上，那么对于任意一条非树边\(e(a,b)\)，若满足a到b的树上路径经过\(e(x,y)\)，
那么，根据最小生成树的性质，添加\(e(a,b)\)后生成的环上的最大边必须是唯一的\(e(a,b)\)。
因此，\(e(x,y)\)的权值应当等于所有满足条件的\(e(a,b)\)的最小权值减1。

2、若x到y不树上，那么，根据最小生成树的性质，添加\(e(x,y)\)后生成的环上的最大边如果不是\(e(x,y)\)，它就能出现。
因此，\(e(x,y)\)的权值应当等于x到y路径上的最大值减1。

2可以使用倍增，\(O(nlogn)\)。

对于1，我们可以把非树边从小到大排序，再依次做链上覆盖，保证每条树边只被其第一次覆盖。
可以把被覆盖的连续边存成一个集合，用并查集维护。

具体来说，并查集的根节点代表此点向上第一个未被覆盖的点（包括自身）。
在这个点被覆盖后，把它与它的父节点的集合合并。

每个点只会被考虑一次，所以复杂度是对的。
总时间复杂度：\(O(nlogn)\)，很好写。

代码：

#include <stdio.h> 
#include <stdlib.h> 
struct SBi {
    int x,  y,  z;
    SBi() {}
    SBi(int X, int Y, int Z) {
        x = X; y = Y; z = Z;
    }
};
SBi bi[200010],px[200010];
int cmp(const void * a, const void * b) {
    return ((SBi * ) a) ->z - ((SBi * ) b) ->z;
}
int fu[200010],fr[200010],ne[400010],v[400010],w[400010],bs = 0;
int getv(int x) {
    if (fu[x] == x) return x;
    fu[x] = getv(fu[x]);
    return fu[x];
}
void addb(int a, int b, int c) {
    v[bs] = b;
    w[bs] = c;
    ne[bs] = fr[a];
    fr[a] = bs++;
}
void kru(int n, int m) {
    for (int i = 1; i <= n; i++) {
        fu[i] = i;
        fr[i] = -1;
    }
    qsort(bi, m, sizeof(SBi), cmp);
    for (int i = 0; i < m; i++) {
        int x = getv(bi[i].x),y = getv(bi[i].y);
        if (x == y) continue;
        fu[x] = y;
        addb(bi[i].x, bi[i].y, bi[i].z);
        addb(bi[i].y, bi[i].x, bi[i].z);
    }
}
int fa[200010],sd[200010],fb[200010],fg[200010];
void dfs1(int u, int f) {
    fa[u] = f;sd[u] = sd[f] + 1;
    for (int i = fr[u]; i != -1; i = ne[i]) {
        if (v[i] != f) {
            fb[v[i]] = w[i];
            dfs1(v[i], u);
        }
    }
}
int x[200010],y[200010],z[200010],bz[18][200010],zd[18][200010];
void yucl(int n) {
    for (int i = 1; i <= n; i++) {
        bz[0][i] = fa[i];
        zd[0][i] = fb[i];
    }
    for (int i = 1; i <= 17; i++) {
        for (int x = 1; x <= n; x++) {
            bz[i][x] = bz[i - 1][bz[i - 1][x]];
            zd[i][x] = zd[i - 1][bz[i - 1][x]];
            if (zd[i - 1][x] > zd[i][x]) zd[i][x] = zd[i - 1][x];
        }
    }
}
int getlca(int a, int b) {
    if (sd[a] < sd[b]) {
        int t = a;
        a = b;b = t;
    }
    for (int i = 17; i >= 0; i--) {
        if (sd[bz[i][a]] >= sd[b]) a = bz[i][a];
    }
    if (a == b) return a;
    int rt;
    for (int i = 17; i >= 0; i--) {
        if (bz[i][a] == bz[i][b]) rt = bz[i][a];
        else {
            a = bz[i][a];
            b = bz[i][b];
        }
    }
    return rt;
}
int getmax(int a, int b) {
    int lc = getlca(a, b),ma = -1;
    for (int i = 17; i >= 0; i--) {
        if (sd[bz[i][a]] >= sd[lc]) {
            if (zd[i][a] > ma) ma = zd[i][a];
            a = bz[i][a];
        }
    }
    for (int i = 17; i >= 0; i--) {
        if (sd[bz[i][b]] >= sd[lc]) {
            if (zd[i][b] > ma) ma = zd[i][b];
            b = bz[i][b];
        }
    }
    return ma;
}
void fugai(int a, int b, int c) {
    while (sd[a = getv(a)] > sd[b]) {
        fg[a] = c;
        fu[a] = getv(fa[a]);
    }
}
int main() {
    int n,m,k = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &x[i], &y[i], &z[i]);
        bi[i] = SBi(x[i], y[i], z[i]);
    }
    kru(n, m);dfs1(1, 0);yucl(n);
    for (int i = 1; i <= n; i++) fu[i] = i;
    for (int i = 0; i < m; i++) {
        int a = x[i],b = y[i];
        if (fa[a] != b && fa[b] != a) bi[k++] = SBi(a, b, z[i]);
    }
    qsort(bi, k, sizeof(SBi), cmp);
    for (int i = 0; i < k; i++) {
        int a = bi[i].x,b = bi[i].y,c = bi[i].z;
        int lc = getlca(a, b);
        fugai(a, lc, c);fugai(b, lc, c);
    }
    for (int i = 0; i < m; i++) {
        int a = x[i],b = y[i];
        if (fa[b] == a) {
            a = y[i];
            b = x[i];
        }
        if (fa[a] != b) printf("%d ", getmax(a, b) - 1);
        else printf("%d ", fg[a] - 1);
    }
    return 0;
}