Kimbap Heaven and Road Hell

Sejin lives in a town with $N$ districts and $M$ roads connecting them. The districts are numbered 1 to $N$. The roads come in three colors: red, yellow, and blue.

Sejin loves kimbap so much that instead of going to Kimbap Heaven himself, he built a delivery robot that can order food for him. The robot never stops moving. It takes exactly 2, 3, and 6 minutes to cross a red, yellow, or blue road, respectively.

Sejin just called Kimbap Heaven and said he will come pick up the food in exactly $K$ minutes. He plans to start the robot from his location right now. Given the town layout, Sejin's location, and the kimbap shop's location, determine whether the robot can follow a route that reaches the shop at exactly minute $K$.

The robot may revisit districts or travel the same road more than once to make the time work out. It may also pass through the district with the shop before arriving. You only need to check whether the robot can be at the shop's location exactly $K$ minutes after it starts.

The first line contains $N$, $M$, and $K$, separated by spaces. $(2 \le N \le 100\,000;$ $N - 1 \le M \le \min(100\,000, 3N(N-1)/2);$ $1 \le K \le 10^9)$

Each of the next $M$ lines contains $i$, $j$, and $w$, separated by spaces. This means there is a road between districts $i$ and $j$ that takes $w$ minutes to cross. $(1 \le i < j \le N;$ $w \in \{2, 3, 6\})$

All roads can be traveled in both directions. Two roads of the same color are never given between the same pair of districts. The roads are given so that every district can be reached from district 1.

The robot always starts at district 1, and the kimbap shop is always at district $N$.

Print YES if the robot can reach the shop at exactly minute $K$, and NO if it cannot.