18193번 - 비행기 타고 가요

정보과학을 잘하는 사람만 거주할 수 있다는 국가, '경곽국'의 존재를 아는가? 경곽국은 총 N개의 도시로 이루어져 있으며, 각각 1번부터 N번까지 번호가 부여되어 있다.

경곽국에서 도시간의 이동수단은 비행기가 유일하다. 모든 도시쌍에 대하여 그 두 도시 사이를 경유하는 비행기가 존재한다. 다만, 비행기를 탑승하기 위해서는 '비행기 표'가 필요하다. 경곽국에서 구매할 수 있는 비행기 표는 총 M개가 있으며, 각각 1번부터 M번까지 번호가 부여되어 있다. i번 표는 가격이 A_i원이며, 비행기의 출발 도시의 번호가 B_i 이상 C_i 이하, 도착 도시의 번호가 D_i 이상 E_i 이하일 때에만 사용할 수 있다(1 ≤ i ≤ M).

모든 M개의 표는 일회용이며 한 번만 구매할 수 있다.

교준이의 집은 K번 도시에 있다. 현재 교준이는 집에서 놀고 있다.

교준이가 집을 나와 X번 도시로 가기 위해 구매해야 하는 표 값의 합의 최솟값을 W_X라 하자(1 ≤ X ≤ N). 단, 교준이는 집을 나오기 전에, 필요한 모든 비행기 표를 구매한다. 만일 어떻게 표를 사서 이동하더라도 X번 도시에 이동할 수 없다면, W_X = -1로 정의한다.

W₁, ···, W_N의 값을 모두 구하는 프로그램을 작성하시오.

첫 번째 줄에 경곽국의 도시의 개수를 의미하는 자연수 N, 비행기 표의 총 개수를 의미하는 자연수 M, 교준이의 집이 있는 도시의 번호 K가 사이에 공백을 두고 주어진다.

두번째 줄부터 M개의 줄에 걸쳐, M개의 비행기 표의 정보가 주어진다. (i+1)번째 줄에는 i번 표의 정보를 나타내는 다섯 개의 정수 A_i, B_i, C_i, D_i, E_i가 사이에 공백을 두고 주어진다(1 ≤ i ≤ M).

첫 번째 줄에 N개의 정수 W₁, ···, W_N를 사이에 공백을 두고 차례대로 출력한다.

W_K = 0임에 유의하라.

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 250,000
• 1 ≤ M ≤ 250,000
• 1 ≤ K ≤ N
• 0 ≤ A_i ≤ 10⁹ (1 ≤ i ≤ M)
• 1 ≤ B_i ≤ C_i ≤ N (1 ≤ i ≤ M)
• 1 ≤ D_i ≤ E_i ≤ N (1 ≤ i ≤ M)