#include #include #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; template struct Graph { struct edge { int to; T r, w; }; int N; vector> G; vector dist; vector prever; Graph(int n) { init(n); } T inf() { if (is_same_v) return 1e9; else return 1e18; } T zero() { return T(0); } void init(int n) { N = n; G.resize(N); dist.resize(N, inf()); } void add_edge(int s, int t, T r, T w) { edge e; e.to = t; e.r = r; e.w = w; G[s].push_back(e); } void dijkstra(int s, T c) { rep(i, 0, N) dist[i] = -1; prever = vector(N, -1); dist[s] = c; priority_queue> q; q.push({c, s}); while (!q.empty()) { int now; T nowdist; tie(nowdist, now) = q.top(); q.pop(); if (dist[now] < nowdist) continue; for (auto e : G[now]) { T cost = nowdist / e.r + e.w; T nextdist = nowdist - cost; if (dist[e.to] < nextdist && nextdist >= 0) { dist[e.to] = nextdist; prever[e.to] = now; q.push({nextdist, e.to}); } } } } vector get_path(int t) { // tへの最短路構築 if (dist[t] >= inf()) return {-1}; vector path; for (; t != -1; t = prever[t]) { path.push_back(t); } reverse(path.begin(), path.end()); return path; } }; int main() { int n, m; ll c; cin >> n >> m >> c; Graph g(n); rep(i, 0, m) { int a, b; ll c, d; cin >> a >> b >> c >> d; a--; b--; g.add_edge(a, b, c, d); g.add_edge(b, a, c, d); } rep(i, 1, c + 1) { g.dijkstra(0, i); cout << g.dist[n - 1] << endl; } }