Minimum Cost Journey

You are given n cities numbered from 1 to n and m bidirectional roads. Each road is described by four integers u, v, l, and c, where u and v denote the cities it connects, l is the distance of the road, and c is its cost.

You are also given a daily travel limit d. A road can only be used if its distance satisfies the inequality \(l \le d\). Your task is to determine the minimum total cost to travel from city 1 to city n using only roads that do not exceed the given distance limit. If it is impossible to reach city n under the given conditions, print -1.

Note: Each road is bidirectional, meaning you can travel in both directions.

inputFormat

The first line contains three integers n, m, and d \( (1 \le n \le 10^5, 1 \le m \le 10^5, 1 \le d \le 10^9)\), representing the number of cities, the number of roads, and the daily distance limit respectively.

Each of the next m lines contains four integers u, v, l, and c \( (1 \le u, v \le n, 1 \le l, c \le 10^9)\) describing a road between cities u and v with distance l and cost c.

outputFormat

Output a single integer representing the minimum total cost to travel from city 1 to city n under the given conditions. If it is not possible to reach city n, output -1.

## sample

5 6 10
1 2 10 100
2 5 10 200
1 3 10 400
1 4 10 300
3 5 10 600
4 5 10 500

300

</p>