tickets_loj

Buying Tickets

This summer, NOI celebrates her 30th birthday in the city of SZ. OIers will travel in from cities all across the country to attend this event in SZ.

The cities of the country form a rooted tree with the city of SZ as its root, and each city is connected to its parent by road. For convenience, we number the $n$ cities with integers from $1$ to $n$. SZ will be city 1, and every other city $v$ is connected to its parent $f_v$ by a road of length $s_v$.

To travel from city $v$ to city SZ, one can choose an ancestor $a$ of city $v$, pay for the ticket, and take the transit to $a$. Then, choose an ancestor $b$ of city $a$, pay for the ticket, arrive at $b$, and so on until you arrive at city SZ.

Each city $v$ also has a distance limit $l_v$ for its transit system. For each ancestor $a$ of city $v$, city $a$ can be reached directly from city $v$ if and only if the total length of all roads between them does not exceed $l_v$. Each city $v$ also has two non-negative integers $p_v$, $q_v$ as fare parameters. If the total length of roads in the path from city $v$ to city $a$ is $d$, then the ticket cost of going directly from city $v$ to city $a$ is $p_{v}d+q_v$.

The OIer in each city wants to arrive in SZ while minimising their spending on tickets. Your task is to tell the OIers in each city what is the minimum amount of money they have to spend.

Limits

$2\le n\le 2\ast {10}^5$, $0\le p_v\le {10}^6$, $0\le q_v\le {10}^{12}$, $1\le f_v<v$, $0<s_v\le l_v\le 2\ast {10}^{11}$.
The distance from any one city to city SZ will not exceed $2\ast {10}^{11}$.
Input $t$ represents the data type. $0\le t\le 3$, where:

• When $t=0$ or $t=2$, all $f_v=v-1$, that is, the cities form a line rooted at SZ.
• When $t=0$ or $t=1$, all $l_v=2\ast {10}^{11}$, that is, there is no distance limit imposed on the cities.
• When $t=3$, none of the above constraints apply.

Subtask #	Score	Constraints
1	10	$n\le 20$
2	20	$n\le 2000$
3	10	$t=0$
4	30	$t=1$
5	10	$t=2$
6	20	No additional constraints

Input format

The first line of input contains two integers $n$, $t$, indicating the number of cities and the data type respectively. (The Data Type is explained under Limits.)

The next $n-1$ lines of input respectively describe cities 2 through $n$. The line describing city $v$ contain 5 non-negative integers $f_v,s_v,p_v,q_v,l_v$, respectively representing the parent of city $v$, the length of the road from $v$ to its parent, the two fare parameters of $v$, and the transit distance limit from $v$.

Output format

Output $n-1$ lines each containing a single integer. Line $v$ must contain the minimum cost of tickets to get from city $v+1$ to SZ.

Samples

Sample Input 1	Sample Output 1
7 3 1 2 20 0 3 1 5 10 100 5 2 4 10 10 10 2 9 1 100 10 3 5 20 100 10 4 4 20 0 10	40 150 70 149 300 150