输在 D 上了，呜呜呜。
首先显然环是没有用的，因此我们只用考虑简单路径。
先思考一个弱化版：如果所有边都已经定向了怎么做。对于每条路径 \(u\to v\)，如果它是一个括号序列，那么我们就用并查集将这条路径上第一条边和最后一条边合并起来，那么颜色数就是并查集连通块数。考虑如何快速合并这个连通性。我们随便给树定一个根，然后对于每条根向的边，我们考虑他到根的路径组成的括号序列。考虑这个括号序列最短的是合法括号串的前缀。如果它存在，那么这个根向的边与这个前缀最后一个字符对应的叶向边可以合并，并且容易证明这个根向边只能和这一个叶向边合并。而我们还能发现一个性质：如果三个点 \(a,b,c\) 满足 \(a\to b,a\to c\) 的路径均是合法括号串，那么 \(b\to c\) 也是合法括号串。这意味着，假设这最短前缀对应的路径为 \(a\to b\)（其中 \(b\) 是 \(a\) 的祖先），且存在另一个与 \(a\) 不构成祖先后代关系的点 \(c\) 满足 \(a\to c\) 是合法括号串，那么也能推出 \(c\to b\) 是合法括号串。也就是说如果我们只将这个根向边与与其对应的叶向边合并，就能维护出这个根向边对应的连通块中的所有点。这样我们将叶向边作为这个连通块的代表元，可知这样的连通块有 \(\text{叶向边个数}\) 个。
但是还存在某些点，满足从这个点出发到根的路径形成的括号序列中，不存在任何一个非空前缀是合法括号串。那么我们记 \(d_i\) 表示从根到 \(i\) 路径上有多少个这样的点，那么容易证明的一件事情是所有 \(d_i\) 相同的点是两两可达的，这样还会贡献 \(\max d_i\) 个等价类。这样总等价类个数就是 \(\text{叶向边个数}+\max d_i\)。如果所有边都已经定向的话，那么我们可以在两遍 DFS 的时间内维护出来，时间复杂度 \(O(n\alpha(n))\)。
现在考虑原问题。一个困难之处在于，括号序列本身其实是一个很难维护的东西；换句话说，它的性质不那么直观，碰到未定向的边时候我们不太好直接判断怎么决策更优，因此我们需要挖掘更强的结论。这就是比较考验脑洞的一步了，我在这里思考了挺长时间。在上文中，考虑将根换到 \(d_i\) 最大的点，这样你发现所有的 \(d_i\) 都变成 \(0\) 了，也就是说，对于所有点，在其到根的路径上都存在一个非空前缀是合法括号串，这样答案就是这种情况下叶向边的个数。而在以任意点为根的情况下，叶向边个数都不会超过答案。这就意味着答案就是在所有点为根的情况下叶向边个数的最大值。这样就好计算最优方案了。枚举一个根，对已经定向的边的贡献是可以树上差分求的，未定向的边定向成叶向边就行了。这样问题就解决了，时间复杂度 \(O(n\alpha(n))\)。
const int MAXN=1e5;
int n,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],val[MAXN*2+5],ec=1,mark[MAXN+5],fa[MAXN+5],sum,R;
void adde(int u,int v,int w){to[++ec]=v;val[ec]=w;nxt[ec]=hd[u];hd[u]=ec;}
struct edge{int typ,u,v;}E[MAXN+5];
void dfs1(int x,int f){fa[x]=f;for(int e=hd[x];e;e=nxt[e]){int y=to[e];if(y==f)continue;dfs1(y,x);}}
void dfs2(int x,int f){for(int e=hd[x];e;e=nxt[e]){int y=to[e];if(y==f)continue;mark[y]+=mark[x];dfs2(y,x);}}
int f[MAXN+5],stk[MAXN+5],tp,col[MAXN+5],ccnt;
int find(int x){return (!f[x])?x:f[x]=find(f[x]);}
void merge(int x,int y){x=find(x);y=find(y);if(x^y)f[x]=y;}
void dfs3(int x,int f){
for(int e=hd[x];e;e=nxt[e]){
int y=to[e],z=val[e],id=e>>1;if(y==f)continue;
if(!~z){z=1;E[id].typ=(x==E[id].u)?1:2;}
if(!z){
int tmp=stk[tp];merge(tmp,id);--tp;
dfs3(y,x);stk[++tp]=tmp;
}else{stk[++tp]=id;dfs3(y,x);--tp;}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].typ);
if(!E[i].typ)adde(E[i].u,E[i].v,-1),adde(E[i].v,E[i].u,-1),sum++;
else adde(E[i].u,E[i].v,1),adde(E[i].v,E[i].u,0);
}
dfs1(1,0);
for(int i=1;i<n;i++)if(E[i].typ){
if(fa[E[i].u]==E[i].v)mark[E[i].u]++;
else mark[1]++,mark[E[i].v]--;
}
dfs2(1,0);pii mx=mp(0,0);
for(int i=1;i<=n;i++)chkmax(mx,mp(mark[i],i));
R=mx.se;printf("%d\n",sum+mx.fi);dfs3(R,0);
for(int i=1;i<n;i++)if(find(i)==i)col[i]=++ccnt;
for(int i=1;i<n;i++){
if(E[i].typ==1)printf("%d %d %d\n",E[i].u,E[i].v,col[find(i)]);
else printf("%d %d %d\n",E[i].v,E[i].u,col[find(i)]);
}
return 0;
}