#include <iostream> #include <queue> #include <vector> using namespace std; using ll = long long; int main() { ll N, M, X; cin >> N >> M >> X; vector<vector<pair<ll, ll>>> g(N); for (int i = 0; i < M; i++) { ll u, v, C, T; cin >> u >> v >> C >> T; u--; v--; g[u].push_back({v, C + T * X}); g[v].push_back({u, C + T * X}); } vector<ll> dist(N, 1e18); dist[0] = 0; priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; pq.push({0, 0}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, w] : g[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } if (dist[N - 1] == 1e18) { cout << -1 << endl; } else { cout << (dist[N - 1] + X - 1) / X << endl; } }