T337711 郝氏机备用线路使用指南

众所周知，在2300年，**[郝氏机](https://www.luogu.com.cn/blog/SqrtSecond/hao-shi-zhiyin-xue-xi-bi-ji)** 早已渗透进我们生活的方方面面，而他的创造者俄思·麦森吉尔（ **[Earth·Messenger](https://www.luogu.com.cn/user/177146)** ）与他的助手斯戈特·赛肯德（ **[Sqrt·Second](https://www.luogu.com.cn/user/217233)** ）在三百年前创造它的原型机时曾遇到了一个问题。

简单来讲，郝氏机的主板上有 $N$ 个接口，每个接口都直接接向信息传输终端，由于郝氏机依靠宇宙射线运作，这些接口必须暴露在宇宙射线中，而宇宙射线不完全可控，所以这些接口可能会突然失效，我们便不能直接从这个接口读取信息了。聪明的麦森吉尔优化了宇宙射线的打击面，使最多同时有一个接口失效。而赛肯德为了完全解决这个问题，在主板背面用导线将接口连成了一个树形结构，此时无论哪个接口失效都可以从另一个接口接收到这个接口的信息，并且这些导线永远不会失效，因为它们用了宇宙射线绝缘材质，因此每条导线会有一个使用代价 $w$，表示使用这条绝缘导线要额外消耗多少单位能源。 但是由于郝氏机跨时优化的特性，这些接口在另一个时空（称之为里世界）与另外 $N$ 个接口一一对应（相对应的接口编号相同），而里世界的赛肯德同样想到了这个方法，他也将接口连成了树形结构，所以信息在导线中传输的代价还要加上在里世界中对应两个接口之间导线的使用代价。**注意，表里世界的导线连接形式和每条导线的使用代价不完全相同。** 现在麦森吉尔希望赛肯德能计算出任意一个接口失效后至少需要额外花费多少代价才能使郝氏机正常运行，以编写《郝氏机备用线路使用指南》，方便用户在接口失效时准备好足够的能源，而赛肯德把这个任务外包给了你。 ### 形式化题意： 有两棵节点数均为 $N$ 的树 $T_1$ 和 $T_2$，边带权，定义 $dist(T,i,j)$ 表示在树 $T$ 中，点 $i,j$ 之间简单路径上的边权和。 对于所有 $1 \le i \le N$，求： $$\min\limits_{j \ne i}\{dist(T_1,i,j)+dist(T_2,i,j)\}$$ 出题人：[六楼溜刘](https://www.luogu.com.cn/user/537230)

第一行一个整数 $N$，表示共有 $N$ 个接口。 第 $2 \sim N$ 行，每行三个整数 $u,v,w$，表示在表世界 $u$ 号接口和 $v$ 号接口之间有一条使用代价为 $w$ 的导线。 第 $N+1 \sim 2N-1$ 行，每行三个整数 $u',v',w'$，表示在里世界 $u'$ 号接口和 $v'$ 号接口之间有一条使用代价为 $w'$ 的导线。 保证输入是两棵树。

共 $N$ 行，第 $i$ 行输出一个整数，表示 $i$ 号接口失效后需要额外花费的代价。

对于 $20\%$ 数据，$N \le 1000$ 另有 $10\%$ 数据，$T_1,T_2$ 均是链。 另有 $10\%$ 数据，$T_1$ 是链。 另有 $10\%$ 数据，$T_1,T_2$ 均是菊花图。 另有 $10\%$ 数据，$T_1$ 是菊花图。 对于 $100\%$ 数据，$2 \le N \le 10^5,1\le u,v,u',v' \le N,1\le w,w' \le 10^9$ 此处对链的定义为：所有结点中，有且仅有两结点度数为 $1$，其余均为 $2$。 此处对菊花图的定义为：所有结点中，有且仅有一个结点度数为 $N-1$，其余均为 $1$。 建议使用 O2 优化。