题目背景

浩瀚的宇宙中分布着无数星际站点，小y驾驶探索飞船开启了全域星际探险。这些星际站点通过星际航道连通，构成了一个特殊的连通结构。小y的飞船有固定的探索规则，她希望遍历星域，统计从每一个站点出发时，有效探索的航道总长度，以此规划最优探险路线。

题目描述

已知星域包含 $n$ 个星际站点、$n$ 条双向星际航道，构成带权无向连通图（基环树结构）。每条航道拥有两个属性：航道长度$w$、航道优先级$p$，所有航道的优先级互不相同。

小y的飞船遵循固定探索规则（类深度优先遍历）：

1. 到达任意一个站点时，优先选择从未行驶过的航道中优先级最高的航道前进；

2. 若当前站点无未行驶的新航道，则沿来时的航道原路返回；

3. 原路返回的航道长度不纳入统计，仅统计首次行驶的航道长度总和。

对于每个起点 $s \in [1,n]$，请你求出从站点 $s$ 出发，按照规则完成全域探索后，累计的有效航道总长度。

输入格式

第一行输入一个整数 $n$，代表星际站点数量（同时等于航道数量）。

接下来 $n$ 行，每行输入四个整数 $u,v,w,p$，表示存在一条连接站点 $u$ 与 $v$ 的双向航道，航道长度为 $w$，优先级为 $p$。

输出格式

输出共 $n$ 行，第 $i$ 行输出一个整数，表示从第 $i$ 号站点出发的有效探索总长度。

5
4 1 2 1
1 2 3 2
3 1 1 4
3 5 2 5
2 3 2 3

7
7
8
7
8

样例解释

1. 从1号站点出发：探索路径为 $1\to3\to5\to2\to4$，有效长度和为 $7$；

2. 从2号站点出发：探索路径为 $2\to3\to5\to1\to4$，有效长度和为 $7$；

3. 从3号站点出发：探索路径为 $3\to5\to1\to2\to4$，有效长度和为 $8$；

4. 从4号站点出发：探索路径为 $4\to1\to3\to5\to2$，有效长度和为 $7$；

5. 从5号站点出发：探索路径为 $5\to3\to1\to2\to4$，有效长度和为 $8$。

数据范围与约定

• $3 \le n \le 10^6$

• $1 \le u,v,p \le n$，所有 $p$ 互不重复

• $0 \le w \le 10^9$