시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 1024 MB250826931.364%

문제

3색 그래프라는 음식을 아는가? 3색 그래프는 경기과학고등학교 학생들의 지친 심신을 위로해주는 보양식으로, 이름에서 알 수 있듯 간편한 조리 방식과 깊은 풍미를 가지고 있어 널리 사랑받는 음식이다. 타 업체의 인기 제품인 <3분 그래프>와의 유사성 논란에도 불구하고 올해는 신제품 <3색 그래프 뿌려먹는 맛>을 출시했다.

신제품 3색 그래프 뿌려먹는 맛. 분말스프가 동봉되어 있다.

3색 그래프는 이름에서 알 수 있듯 정점 $N$개, 간선 $M$개의 가중치 있는 무방향 단순 연결그래프의 형태이며, 각 간선에는 검정색, 파란색, 빨간색의 3가지 색이 칠해져 있다. 또, 그래프와 함께 분말스프가 $X$스푼 포장되어 있는데, 분말스프를 빨간색 간선에 한 스푼 뿌리면 모든 빨간색 간선들의 가중치가 1씩 증가하고, 파란색 간선에 한 스푼 뿌리면 모든 파란색 간선들의 가중치가 1씩 증가한다.

큰 마음먹고 3색 그래프를 구매한 한별이는 $1$번 정점에서 $N$번 정점으로 가는 최단경로의 길이가 길수록 그래프가 더 맛있다고 생각한다. 한별이를 도와 총 $X$스푼 이하로 빨간색 간선들과 파란색 간선들에 분말스프를 뿌려 그래프를 최대한 맛있게 즐길 수 있도록 도와주자.

입력

첫 번째 줄에 $N$, $M$, $X$가 공백을 사이에 두고 주어진다. ($1 \leq N \leq 200,000$, $N-1 \leq M \leq 200,000$, $0 \leq X \leq 10^9$)

두 번째 줄부터 $M$개의 줄에 걸쳐 $u$, $v$, $w$, $p$가 사이에 공백을 두고 주어지는데, 이는 $u$ 정점과 $v$ 정점을 가중치 $w$이고 색 $p$인 간선이 연결한다는 의미이다. $p=0$은 검정색, $p=1$은 빨간색, $p=2$는 파란색을 의미한다. ($1 \leq u, v \leq N$, $0 \leq w \leq 10^9$, $0 \leq p \leq 2$) 

그래프는 단순 연결그래프임이 보장된다. 구체적으로, 그래프에는 $u$번 정점과 $u$번 정점을 잇는 간선이 존재하지 않으며, 어떠한 두 쌍의 정점들에 대하여 최대 1개의 간선만 존재한다. 또한, 임의의 두 정점에 대하여 간선만을 이용하여 서로 이동할 수 있는 경로가 존재한다.

출력

첫 번째 줄에 $1$번 정점에서 $N$번 정점으로 가는 최단경로의 길이의 최대값을 출력한다.

예제 입력 1

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

예제 출력 1

18

예제 입력 2

6 8 12
2 5 7 2
1 4 20 1
3 6 2 2
2 3 16 0
2 4 9 1
5 3 12 0
1 3 12 1
4 3 15 2

예제 출력 2

26

예제 입력 3

10 15 107
7 6 733 2
4 9 130 2
5 3 176 1
10 8 178 2
6 9 643 2
6 4 769 1
5 7 465 2
7 2 630 2
1 4 942 1
3 9 284 1
9 10 989 2
8 5 910 1
10 7 717 2
10 6 251 2
2 3 618 0

예제 출력 3

2141

출처

High School > 경기과학고등학교 > 나는코더다 2021 송년대회 B번