#include <bits/stdc++.h>
// #define int long long

#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
typedef pair<int, int> Pair;

const int N = 500005;
int n, m, s, cnt, r0, r1, dis[N << 3], v[N << 3];
vector<Pair> G[N << 3];
struct SegmentTree {
    int ls, rs;
} t[N << 3];
void build0(int &p, int l = 1, int r = n) {
    if (l == r) {
        p = l; return ;
    } else p = ++cnt;
    int mid = l + r >> 1;
    build0(t[p].ls, l, mid);
    build0(t[p].rs, mid + 1, r);
    G[t[p].ls].push_back({p, 0});
    G[t[p].rs].push_back({p, 0});
}
void build1(int &p, int l = 1, int r = n) {
    if (l == r) {
        p = l; return ;
    } else p = ++cnt;
    int mid = l + r >> 1;
    build1(t[p].ls, l, mid);
    build1(t[p].rs, mid + 1, r);
    G[p].push_back({t[p].ls, 0});
    G[p].push_back({t[p].rs, 0});
}
void link(int p, int x, int y, int u, int w, int id, int l = 1, int r = n) {
    if (x <= l && r <= y) {
        if (id) G[u].push_back({p, w});
        else G[p].push_back({u, w});
        return ;
    }
    int mid = l + r >> 1;
    if (x <= mid) link(t[p].ls, x, y, u, w, id, l, mid);
    if (y > mid) link(t[p].rs, x, y, u, w, id, mid + 1, r);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    cnt = n;
    build0(r0);
    build1(r1);
    // cerr << cnt << ' ';
    while (m --) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cnt ++;
        link(r1, a, b, cnt, 0, 0);
        link(r0, c, d, cnt, 1, 1);
        cnt ++;
        link(r1, c, d, cnt, 0, 0);
        link(r0, a, b, cnt, 1, 1);
        // F(i, a, b) {
        //     F(j, c, d) {
        //         G[i].push_back({j, 1});
        //         G[j].push_back({i, 1});
        //     }
        // }
    }
    memset(dis, 0x3f, sizeof dis);
    priority_queue<Pair> q;
    // -dis, now
    q.push({0, s}), dis[s] = 0;
    while (q.size()) {
        int now = q.top().second;
        q.pop();
        if (v[now]) continue;
        v[now] = 1;
        for (auto i : G[now]) {
            int v = i.first, w = i.second;
            if (dis[now] + w < dis[v]) {
                dis[v] = dis[now] + w;
                q.push({-dis[v], v});
            }
        }
    }
    F(i, 1, n) cout << dis[i] << '\n';
    return 0;
}