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 nonnegative 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.
Subtask #  Score  Constraints 

1  10  \(n \leq 20\) 
2  20  \(n \leq 2000\) 
3  10  \(t = 0\) 
4  30  \(t = 1\) 
5  10  \(t = 2\) 
6  20  No additional constraints 
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 nonnegative 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 \(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.
Sample Input 1  Sample Output 1 
7 3

40

Subtask  Score 

1  10 
2  20 
3  10 
4  30 
5  10 
6  20 
7  0 