P6037 Ryoku 的探索

Ryoku 对自己所处的世界充满了好奇，她希望能够在她「死」之前尽可能能多地探索世界。 这一天，Ryoku 得到了一张这个世界的地图，她十分高兴。然而，Ryoku 并不知道自己所处的位置到底在哪里，她也不知道她会什么时候死去。她想要知道如何才能尽可能多的探索这个世界。

Ryoku 所处的世界可以抽象成一个有 $n$ 个点， $n$ 条边的带权无向连通图 $G$。每条边有美观度和长度。 Ryoku 会使用这样一个策略探索世界：在每个点寻找一个**端点她未走过**的边中**美观度最高**的走，如果没有边走，就沿着她前往这个点的边返回，类似于图的**深度优先遍历**。 探索的一个方案的长度是这个方案所经过的所有边长度的和（返回时经过的长度不用计算）。 她想知道，对于每一个起点 $s=1,2,\cdots,n$，她需要走过的长度是多少？

无

无

**【样例 1 说明】** 以下为输入输出样例 1 中的图： （边上红色数组为 $p$，黑色为 $w$）  若起点为 $1$，顺序为 $1\to3\to5\to2\to4$，长度之和为 $7$。 若起点为 $2$，顺序为 $2\to3\to5\to1\to4$，长度之和为 $7$。 若起点为 $3$，顺序为 $3\to5\to1\to2\to4$，长度之和为 $8$。 若起点为 $4$，顺序为 $4\to1\to3\to5\to2$，长度之和为 $7$。 若起点为 $5$，顺序为 $5\to3\to1\to2\to4$，长度之和为 $8$。 --- **【数据规模与约定】** 对于 $40\%$ 的数据，$n\le 10^3$。 对于 $100\%$ 的数据，$3 \le n \le 10^6$，$1 \le u,v,p \le n$，$0\le w\le 10^9$，保证 $p$ 互不相同。