24024번 - 삼색 그래프

문제

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$번 정점으로 가는 최단경로의 길이의 최대값을 출력한다.

제한

힌트