Description

This Summer, NOI is celebrating its 30th birthday in the city of SZ(Shenzhen). OIers attending this ceremony are travelling to SZ from $n$ cities around the country.

The cities in the country form a rooted tree with SZ as its root, and each city is connected to its parent by a road. For simplicity, we label the $n$ cities with integers from $1$ to $n$. SZ city has a label of $1$. For any city other than SZ labelled $v$, its parent on the tree $f_v$ and length of the road to its parent $S_v$ is given.

To arrive in SZ from city $v$, we first choose one of $v$'s ancestors, $a$, and pay for a ticket to $a$. Then we choose $a$'s ancestor $b$ and pay to arrive in $b$. Repeat this process until SZ is reached.

For each city $v$, a limit on travel distance $l_v$ is given. For $a$ as an ancestor of $v$, a direct transportation from city $v$ to city $a$ could be taken only if the sum of roads' distances between them is not greater than $l_v$; otherwise it cannot be reached within one travel. For each city $v$, parameters of transportation price $p_v,q_v$ are also known. if the total distance of roads from city $v$ to city $a$ is $d$, then the price of ticket from city $v$ to city $a$ is $dp_v+q_v$.

OIers from every city want to spend less money to get to SZ. Your task is to tell them the minimum cost for OIers in each city.

Input Format

The first line contains two integers $n,t$, indicating the number of cities and a brief description of input data (meaning explained later).

Each line from line $2$ to line $n$ describes a city other than SZ. Line $v$ consists of five non-negative integers $f_v,S_v,p_v,q_v,l_v$, indicating the parent of city $v$, the distance between them, the two parameters for ticket price, and the limitation on travel distance respectively.

Note: Input does not contain city $1$, SZ. line $2$ to line $n$ describes city $2$ to city $n$.

Output Format

The output consists of $n-1$ lines, each with one integer. Line $v$ is the minimum cost to travel from city $v+1$ to SZ.

Also Note: Output does not contain city $1$, SZ.

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

Constraints and Hint

For all the data, $n \leq 2 \times 10^5$, $0 \leq p_v \leq 10^6$, $0 \leq q_v \leq 10^{12}$, $1 \leq f_v < v$, $0 < s_v \leq l_v \leq 2 \times 10^{11}$, and the total distance from any city to SZ is not greater than $2 \times 10^{11}$.

$t$ in input describes input type, $0 \leq t < 4$:

When $t=0$ or $2$, for every city $v$ in input, $f_v=v-1$, therefore the cities form a chain with SZ on one end;

When $t=0$ or $2$, for every city $v$ in input, $l_v=2 \times 10^{11}$, therefore there's no limit on travel distance, all cities could travel directly to any of their ancestors;

When $t=3$, no special case is expected.