Take the Plane

Have you heard of Gyeonggwak, a country where only people good at computer science may live? Gyeonggwak has $N$ cities, numbered from 1 to $N$.

The only way to travel between cities in Gyeonggwak is by airplane. For every pair of cities, a flight passes between the two. However, boarding a flight requires an airplane ticket. Gyeonggwak sells $M$ tickets, numbered from 1 to $M$. Ticket $i$ costs $A_i$ won and can be used only when the departure city number is between $B_i$ and $C_i$ inclusive, and the arrival city number is between $D_i$ and $E_i$ inclusive ($1 \le i \le M$).

Each of the $M$ tickets is single-use and can be bought only once.

Junjun's house is in city $K$. Right now, Junjun is staying at home.

Let $W_X$ be the minimum total cost of tickets Junjun must buy to travel from his house to city $X$ ($1 \le X \le N$). Junjun buys all the necessary tickets before leaving home. If no way of buying tickets lets him reach city $X$, define $W_X = -1$.

Write a program that computes all of $W_1, \cdots, W_N$.

The first line contains three integers $N$, $M$, and $K$, separated by spaces.

From the second line onward, the next $M$ lines describe the tickets. Line $(i+1)$ contains five integers $A_i$, $B_i$, $C_i$, $D_i$, and $E_i$, separated by spaces ($1 \le i \le M$).

Print $N$ integers $W_1, \cdots, W_N$ on one line, separated by spaces.

Note that $W_K = 0$.

• $1 \le N \le 250{,}000$
• $1 \le M \le 250{,}000$
• $1 \le K \le N$
• $0 \le A_i \le 10^9$ ($1 \le i \le M$)
• $1 \le B_i \le C_i \le N$ ($1 \le i \le M$)
• $1 \le D_i \le E_i \le N$ ($1 \le i \le M$)