Minimum Special Roads

You are given a network of (N) cities and (M) bidirectional roads. Each road connects two cities and has an associated toll cost and a type indicator. A road of type 1 is considered a special road, while type 0 indicates a normal road. Your task is to determine the minimum number of special roads required in a path from city 1 to city (N). If there is no path from city 1 to city (N), output -1.

In more formal terms, given a graph (G=(V,E)) with (|V|=N) and (|E|=M) where each edge (e) has a toll cost (c(e)) and an indicator (\delta(e)) defined by: [ \delta(e)=\begin{cases} 1, & \text{if the road is special}\ 0, & \text{otherwise} \end{cases} ] find a path (P) from vertex 1 to vertex (N) that minimizes (\sum_{e \in P} \delta(e)). If no such path exists, output -1.

Note that the value (K) provided in the input is not used in the computation but is part of the input format.

inputFormat

The input is given via standard input (stdin). The first line contains three integers (N), (M), and (K), where (N) represents the number of cities, (M) represents the number of roads, and (K) is an extra parameter. Each of the next (M) lines contains four integers (u), (v), (toll), and (type). Here, (u) and (v) are the cities connected by the road, (toll) is the toll cost of that road, and (type) is either 1 (special road) or 0 (normal road).

outputFormat

Print a single integer on standard output (stdout): the minimum number of special roads used in a valid path from city 1 to city (N). If no such path exists, print -1.## sample

5 6 2
1 2 1 1
2 3 1 0
3 5 1 0
2 4 2 1
4 5 1 0
1 3 3 0

1