#include <iostream>
#include <cstdio>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
const int N = 1000010;
struct edge{ int a, b, c; }e[N];
bool operator < (const edge &a, const edge &b) { return a.c < b.c; }
int n, m;
#define pb(a) push_back(a)
struct us{
vector<int> fa[N], sz;
void init(){ fa.clear(); rep(i,1,sz) fa[i].pb(i); }
int find(int x) { return fa[x] == x ? x : f[x] = find(f[x]); }
}mst;
bool vis[N];
namespace Graph{
struct edge{ int to, pre; }e[N * 2]; int u[N], l = 0;
void ins(int a, int b) { e[++l] = (edge){b, u[a]}, u[a] = l; }
#define v e[i].to
#define reg(i,a) for(int i = u[a]; i; i = e[i].pre)
void
}
int main() {
scanf("%d%d",&n,&m);
rep(i,1,m) scanf("%d%d%d",&e[i].a,&e[i].c,&e[i].c);
sort(e + 1, e + m + 1); mst.sz = n; mst.init(); int mx = 0;
rep(i,1,m) {
int fa = mst.find(e[i].a), fb = mst.find(e[i].b);
if (fa != fb) { vis[i] = true; mx = i; mst.fa[fa] = fb; Graph::ins(e[i].a, e[i].b), Graph::ins(e[i].b, e[i].a); }
}
rep(i,1,n) ans[i] = -1;
rep(i,1,mx) if (!vis[i]) addedge(e[i].a, e[i].b, i);
rep(i,1,n) if (ans[i] != -1) ans[i] = mx;
rep(i,mx+1,m) addedge(e[i].a, e[i].b, i);
rep(i,1,n) printf("%d ",ans[i] == -1 ? -1 : e[ans[i]].c); printf("\n");
return 0;
}
2016年6月24日 23:19
http://paste.ubuntu.com/17848373/