#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll oo = 2e18;
const int B = 100;
const int N = 1e5+5;
const int NODES = 5e5+5;

struct Edge {
    int to;
    ll w;
};

int n, m, c, S[B], bup[B][N], bdown[B][N];
vector<Edge> adj[NODES];
vector<int> st[B], up[B], down[B];
ll dist[NODES];

void solve() {
    cin >> n >> m >> c;

    int nodes = n + m;
    for (int d = 1; d < B; d++) {
        int S_d = max(1, (int)sqrt(n / (2.0 * d)));
        S[d] = S_d;
        st[d].assign(d + 1, 0);
        int blocks = 0;
        for (int r = 0; r < d; r++) {
            int cnt = 0;
            for (int x = r; x <= n; x += d)
                if (x >= 1) cnt++;
            int b = (cnt + S_d - 1) / S_d;
            st[d][r] = blocks;
            blocks += b;
        }
        up[d].resize(blocks);
        down[d].resize(blocks);
        for (int i = 0; i < blocks; i++) {
            up[d][i] = ++nodes;
            down[d][i] = ++nodes;
        }
    }

    for (int i = 1; i < n; i++) {
        adj[i].push_back({i + 1, c});
        adj[i + 1].push_back({i, c});
    }

    for (int d = 1; d < B; d++) {
        int S_d = S[d];
        for (int x = 1; x <= n; x++) {
            int r = x % d;
            int first = (r == 0 ? d : r);
            int idx = (x - first) / d;
            int b = idx / S_d;
            int bid = st[d][r] + b;
            int u = up[d][bid], v = down[d][bid];
            bup[d][x] = u, bdown[d][x] = v;
            adj[x].push_back({u, 0});
            adj[v].push_back({x, 0});
        }
    }

    for (int i = 1; i <= m; i++) {
        int l, d, k, t; cin >> l >> d >> k >> t;
        int R = l + k * d, V = n + i;
        if (d >= B) {
            for (int j = 0; j <= k; j++) {
                int x = l + j * d;
                if (x > n) break;
                adj[x].push_back({V, t});
                adj[V].push_back({x, 0});
            }
        } else {
            int S_d = S[d];
            int r = l % d;
            int first = (r == 0 ? d : r);
            int idx_s = (l - first) / d, idx_e = (R - first) / d;
            int b_s = idx_s / S_d, b_e = idx_e / S_d;
            if (b_s == b_e) {
                for (int idx = idx_s; idx <= idx_e; idx++) {
                    int x = first + idx * d;
                    adj[x].push_back({V, t});
                    adj[V].push_back({x, 0});
                }
            } else {
                int end_i = (b_s + 1) * S_d - 1;
                for (int idx = idx_s; idx <= end_i; idx++) {
                    int x = first + idx * d;
                    adj[x].push_back({V, t});
                    adj[V].push_back({x, 0});
                }
                for (int b = b_s + 1; b <= b_e - 1; b++) {
                    int u = bup[d][first + b * S_d * d], v = bdown[d][first + b * S_d * d];
                    adj[u].push_back({V, t});
                    adj[V].push_back({v, 0});
                }
                int start_i = b_e * S_d;
                for (int idx = start_i; idx <= idx_e; idx++) {
                    int x = first + idx * d;
                    adj[x].push_back({V, t});
                    adj[V].push_back({x, 0});
                }
            }
        }
    }

    for (int i = 1; i <= nodes; i++) dist[i] = oo;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

    dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (Edge& e : adj[u]) {
            int v = e.to, w = e.w;
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (dist[i] == oo) cout << "-1 ";
        else cout << dist[i] << " ";
    }
    cout << "\n";
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int tests = 1; // cin >> tests;
    while (tests--) solve();

    #ifndef ONLINE_JUDGE
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif

    return 0;
}