U464052 『凌日潮汐OI』T3 - Destruction 3,2,1
题目背景
“~~你也许也意识到了这件事，~~\
“~~旅船是掩盖未来的虚像，战车正指引我们的命运，~~\
“~~硬币掷出之后，正逆的转换从未停止，~~\
“~~前方是毁灭亦是重生。~~\
\
\
......\
\
\
“**PhigrOS**已崩溃，感谢您的参与，愿我们在塔中重聚。\
本题为原题改题面题，故不用于出成公开赛
题目描述
幽蓝边界已经吞噬了大量的数据，碎数研正在重新想办法反击\
目前PhigrOS的节点共有 $ N $ 个，之间用 $ N - 1 $ 条优先级极高的边连接（不需要额外访问时间），为了防止幽蓝边界破坏后相互失联，碎数研还额外加了 $ M $ 条边，但这些边的访问优先级很低，第 $ i $ 条边需要 $ w_i $ 的额外访问时间\
所以碎数研要考虑加固某些原有的边，你的任务就是检查某条原有的边被破坏后，这条原有的边两个点之间新的额外访问时间\
形式化题面：\
给定一棵无根树，树上边权均为 $ 0 $ ，再在树上添加若干条无向有权边，问删除原树上每一条边（每次只删一条边，删完复原）后，原边相接的两点间最短距离
输入格式
第一行一个整数 $ N $ ，表示节点数。\
接下来 $ N - 1 $ 行，每行两个整数 $ a_i , b_i $ 表示相连的一条优先级极高的边。\
接下来一个整数 $ M $ ，表示新加的边数量。\
接下来 $ M $ 行，每行三个整数 $ a _ i , b _ i , w _ i $ ，分别表示相连的一点和另一点，以及额外访问时间。
输出格式
共 $ N - 1 $ 行，按照输入里原有边的输入顺序，每行一个整数，表示这条边如果删除两个相邻点的访问时间，如果无法访问，输出 $ -1 $
说明/提示
对于 $ 5 \% $ 的数据， $ N,M \le 100 $ \
对于 $ 25 \% $ 的数据， $ N,M \le 1000 $ \
对于额外 $ 20 \% $ 的数据，每条额外连接的边的一对点在原图的距离不超过 $ 2 $ 条原边\
对于再额外 $ 5 \% $ 的数据， $ M = 0 $ \
对于再额外 $ 15 \% $ 的数据，图是链\
对于 $ 100 \% $ 的数据， $ N,M \le 1 \times 10^5 , w_i \le 10^9 $