승현이는 자신이 금상을 받은 것을 알고 절망에 빠졌습니다. 그는 분명히 모든 답안을 정해로 만들어 제출했기 때문입니다. 이 모든 것이 자신을 없애려는 음모라고 생각한 승현이는 최대한 빨리 NIA에 침입하여 KOI 담당자님을 직접 만나 보려고 합니다. 그러나 그의 부모님께서 용돈을 끊어 버려 돈이 없는 그는 분당에서 NIA까지 걸어가야 합니다.

서울특별시의 도로 지도는 아래 그림과 같이 그래프 형태로 나타낼 수 있습니다. 여기서 도로는 ‘사람이 지나다닐 수 있는 도로’를 의미합니다. 그래프는 V개의 정점과 E개의 간선(도로)으로 구성되며, 각 정점에는 1부터 V까지의 번호가 붙어 있고, 두 정점 사이에는 많아야 1개의 도로만 있을 수 있습니다. 현재 승현이는 1번 정점에 있고, NIA는 V번 정점에 있습니다. 사람의 혼잡을 방지하기 위해, 각 정점에 연결될 수 있는 도로의 수는 최대 4개입니다.

[그림 1] V = 7일 때의 예입니다. 승현이는 1번 정점에서 7번 정점까지 가야 합니다.

도로에는 2가지의 종류가 있습니다.

• 인도 - 인도는 승현이가 언제나 지나다닐 수 있습니다.
• 건널목 - 이 도시의 모든 건널목에는 신호등이 설치되어 있습니다. 합법적으로 건널목을 건너기 위해서는 건널목을 건너는 동안 그 건널목의 신호등이 계속 초록 불이어야 합니다.

i번 도로가 건널목일 때, 이 건널목의 각 신호등은 아래와 같이 동작합니다.

• a_i초 동안 빨간 불이 됩니다. 승현이가 무단 횡단을 하고 싶다면 이 시간 동안 건널목을 건너면 됩니다. 건널목을 건너다가 단 1초 동안이라도 신호등이 빨간 불이 되면 이는 ‘무단 횡단’입니다.
• 빨간 불이 켜진 지 a_i초가 지난 순간, b_i초 동안 초록 불이 됩니다. 승현이가 합법적으로 건널목을 건너려면 이 시간 동안 건널목을 모두 건너야 합니다.
• 위 두 동작을 반복합니다. 여기서 a_i, b_i는 자연수입니다.
• 명확하게 하기 위해 수직선으로 나타내면 [그림 2]와 같습니다. 빨간색 부분은 신호등이 빨간 불인 시간, 초록색 부분은 신호등이 초록 불인 시간을 의미합니다.

[그림 2] x+a_i+b_i초에 정확히 도착할 수 있더라도 무단 횡단을 하지 않고 건널목을 건널 수 있습니다.

[그림 1]에서 도로 옆에 표시된 숫자는 승현이가 그 도로를 지나가는 시간(초 단위)입니다. (승현이는 체력이 매우 좋아서 아무리 돌아다녀도 속도가 줄지는 않으므로, 그것에 대해서는 고려할 필요가 없습니다.)

승현이는 최대한 빨리 담당자와 1:1로 대면하고 싶어서, 마음 같아서는 모든 건널목을 무단 횡단하고 싶지만, 경찰이 단속을 벌이고 있어 최대 K번까지만 무단 횡단을 할 수 있습니다.

위의 조건들을 모두 만족하며 승현이가 NIA에 도착할 수 있는 가장 짧은 시간을 출력하는 프로그램을 작성하세요.

입력

첫째 줄에 정점의 수 V(1≤V≤100,000), 도로의 수 E와 무단 횡단을 할 수 있는 최대 횟수 K(0≤K≤3)가 공백을 사이로 두고 주어집니다.
다음 E개의 줄에 각 도로의 정보가 한 줄에 하나씩 아래와 같이 주어집니다.

• 인도인 경우, “0 u v t_i”(단 1≤u,v≤V, 0<t_i≤1,000)가 주어집니다.
  이는 정점 u와 정점 v 사이에 승현이가 지나가는 데 t_i초가 걸리는 인도가 있다는 것을 의미합니다.
• 건널목인 경우, “1 u v s_i a_i b_i t_i”(단 1≤u,v≤V, 1≤a_i ,b_i≤1,000, 0≤_i<a_i+b_i,0<t_i<b_i)가 주어집니다.
  이는 정점 u와 정점 v 사이에 승현이가 지나가는 데 t_i초가 걸리는 건널목이 있고, 이 건널목의 신호등이 승현이가 출발하는 시각에서 s_i초 전부터 a_i초 동안 빨간 불이 되었다가, b_i초 동안 초록 불이 되는 과정을 반복한다는 것을 의미합니다.

출력

첫째 줄에 승현이가 1번 정점에서 출발해서 V번 정점까지 도착하는 데 걸리는 최소 시간을 출력합니다. 도로를 통해 도착이 불가능한 경우 “-1”을 출력합니다.

입출력 예

입력

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

출력

13

입출력 보충

정점 4와 정점 5를 잇는 도로를 무단 횡단 하면 한 번도 신호등에 걸리지 않고 3+4+3+3=13초만에 NIA로 도착할 수 있습니다. 입출력 데이터는 [그림 1]과 같습니다.

출처:GENIUSainta.com