30628번 - 김밥천국과 도로지옥

세진이가 살고 있는 마을은 $N$개의 구역이 있고, 각 구역을 잇는 도로가 총 $M$개 존재한다. 각 구역에는 $1$번부터 $N$번까지 차례대로 번호가 붙는다. 또한, 도로에는 빨간색, 노란색, 파란색의 세 종류의 도로가 있다.

김밥을 너무 좋아하는 세진이는 자신이 직접 김밥천국에 가지 않고 김밥을 주문할 수 있는 김밥 배달 전문 로봇을 만들었다. 이 로봇은 절대 멈추지 않고 움직이며 빨간색, 노란색, 파란색 도로를 지나가는 데 각각 정확히 $2$분, $3$분, $6$분이 걸린다.

세진이는 지금 막 김밥천국에 전화해 정확히 $K$분 후에 김밥을 찾으러 가겠다고 말했다. 세진이는 지금 당장 로봇을 자신의 위치에서 출발시킬 예정이다. 마을의 구조, 세진이의 위치, 김밥집의 위치를 고려해서 정확히 $K$분 후에 로봇이 김밥집에 도달할 수 있게 로봇의 이동 경로를 짜는 것이 가능할지 생각해 보자.

참고로, $K$분을 맞추기 위해 같은 구역을 재방문하거나 같은 도로를 두 번 이상 지나는 것도 가능하며, 김밥집이 있는 구역을 중간에 지나치는 것도 가능하다. 정확히 $K$분 후에 로봇이 김밥집의 위치에 있을 수 있는지만 확인하면 된다.

첫 번째 줄에 구역의 개수 $N$과 도로의 개수 $M$, 그리고 정수 $K$가 공백으로 구분되어 주어진다. $(2 \le N \le 100\,000;$ $N - 1 \le M \le \min(100\,000, 3N(N-1)/2);$ $1 \le K \le 10^9)$

두 번째 줄부터 $M + 1$번째 줄까지 정수 $i$, $j$, $w$가 공백으로 구분되어 주어진다. 각각 $i$번과 $j$번 사이에 건너는 데 $w$분이 걸리는 도로가 있음을 의미한다. $(1 \le i < j\le N;$ $w\in\{2, 3, 6\})$

모든 도로는 양방향으로 통행할 수 있고, 임의의 두 구역 사이를 잇는 같은 색의 도로는 두 번 주어지지 않으며, $1$번 구역에서 출발해 모든 구역에 도달할 수 있게 도로가 주어진다.

문제에서 로봇의 최초 위치는 항상 $1$번 구역이며, 김밥집의 위치는 항상 $N$번 구역이다.

이동 경로를 짜는 것이 가능하면 YES를, 불가능하면 NO를 출력한다.