#include // cout, endl, cin #include // string, to_string, stoi #include // vector #include // min, max, swap, sort, reverse, lower_bound, upper_bound #include // pair, make_pair #include // tuple, make_tuple #include // int64_t, int*_t #include // printf #include // map #include // queue, priority_queue #include // set #include // stack #include // deque #include // unordered_map #include // unordered_set #include // bitset #include // isupper, islower, isdigit, toupper, tolower #include #include #include #include #include #include #include #include #include //#include //using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep1(i, n) for (int i = 1; i <= (int)(n); i++) #define repl(i,l,r) for (int i = l; i < (int)(r); i++) #define all(a) a.begin(),a.end() #define Pii pair #define Pll pair #define INFi 1000000001 #define INFl 10000000000001 #define ll long long using namespace std; template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template void printArray(vector&A){ for(T&a:A){ cout< void printArrayln(vector&A){ for(T&a:A){ cout< std::ostream &operator<<(std::ostream &out, const pair &A){ cout<<"{"< std::ostream &operator<<(std::ostream &out, const map &M){ for(const auto&A:M){ cout<<"{"< std::ostream &operator<<(std::ostream &out, const set &M){ cout<<"{"; for(const auto&A:M){ cout< std::ostream &operator<<(std::ostream &out, const multiset &M){ cout<<"{"; for(const auto&A:M){ cout< std::ostream &operator<<(std::ostream &out, const vector &A){ for(const T &a:A){ cout< void print(Head H, Tail... T) { cout << H << " "; print(T...); } template std::istream &operator>>(std::istream &in,vector&A){ for(T&a:A){ std::cin>>a; } return in; } struct Edge{ int to; long cost; long time; }; using Graph = vector>; long X; struct State{ int v; long cost; long time; bool operator>(const State &s) const{ int l = time+(cost+X-1)/X; int r = s.time+(s.cost+X-1)/X; if(l==r){ return cost>s.cost; } return l>r; } }; int main(void){ std::cin.tie(0)->sync_with_stdio(0); int N,M;cin>>N>>M>>X; Graph G(N); rep(i,M){ int a,b,c,t;cin>>a>>b>>c>>t; a--;b--; G[a].push_back({b,c,t}); G[b].push_back({a,c,t}); } priority_queue,greater> pq; pq.push({0,0,0}); vector dist(N,{0,-1,-1}); dist[0]={0,0,0}; while(!pq.empty()){ State s=pq.top();pq.pop(); for(Edge e:G[s.v]){ long t = s.time+e.time; long m = s.cost+e.cost; State next = {e.to,m,t}; if(dist[e.to]>next || dist[e.to].time==-1){ dist[e.to]=next; pq.push(next); } } } if(dist[N-1].time==-1){ cout<<-1<