题目描述

C 国拥有一张四通八达的高速公路树。

C 国有 $n$ 个城市，城市之间由一共 $n-1$ 条高速公路连接。除了首都 $1$ 号城市，每个城市都有一家本地的客运公司，可以发车前往全国各地。你可以把它认作以 $1$ 为根的树。两城市的距离定义为它们之间简单路径的长度。

假设有一个人要从 $i$ 号城市坐车出发前往与其距离为 $D$ 的 $j$ 号城市，那么他要花费 $P_i \times D+Q_i$ 元。由于距离首都越远，国家的监管就越松，所以距离首都越远，客运公司的 $P_i$ 越大，如果 $i$ 号城市是 $j$ 号城市的某个祖先，那么一定存在 $P_i \leq P_j$。

小 T 成为了国家统计局的调查人员，他需要对现在的高速路网进行一次调查，了解从其他每一个城市到达首都 $1$ 号城市所花费的金钱。

因为可能出现多转车（或不转车）的抵达首都的方法，所以人工计算这个结果是十分复杂的。大宁非常的懒，所以请你编写一个程序解决它。

输入格式

第 $1$ 行包含一个整数 $n$，表示城市的个数。

第 $2$ 到 $n$ 行，每行描述一个除首都之外的城市。其中第 $i$ 行包含 $4$ 个整数 $F_i,S_i,P_i,Q_i$，分别表示 $i$ 号城市的父亲城市，它到父亲城市高速公路的长度，以及乘车价格的两个参数。

输出格式

输出包含 $n-1$ 行，每行包含一个整数。

其中第 $i$ 行表示从 $i+1$ 号城市出发，到达首都最少的乘车费用。

6
1 9 3 0
1 17 1 9
1 1 1 6
4 13 2 15
4 9 2 4

27
26
7
43
24

提示

数据规模与约定

• 对于前 $40\%$ 的数据 $n \leq 1000$。
• 对于另外 $20\%$ 的数据，$F_i=i-1$
• 对于所有的数据，$1 \leq n \leq 10^6$，$0 \leq Pi,Qi \lt 2^{31}$，保证结果不会大于 $2^{63}-1$。