#include <bits/stdc++.h>   using namespace std;   const int MAX = 2e6 + 5;   const int MAXN = 7e6 + 5;   const long long INF = 0x3f3f3f3f3f3f3f3f;   int n, q, s, first[MAX], nextt[MAXN], u[MAXN], v[MAXN], cnt;   long long w[MAXN];   void add(int a, int b, long long c) {     u[cnt] = a, v[cnt] = b, w[cnt] = c;     nextt[cnt] = first[u[cnt]];     first[u[cnt]] = cnt;     ++cnt;   }   void build_tree_one(int p, int l, int r) {     if (l == r) {       add(p + 4 * n, l, 0);       return;     }     int mid = (l + r) >> 1;     add(p + 4 * n, (p << 1) + 4 * n, 0);     add(p + 4 * n, (p << 1 | 1) + 4 * n, 0);     build_tree_one(p << 1, l, mid);     build_tree_one(p << 1 | 1, mid + 1, r);   }   void build_tree_two(int p, int l, int r) {     if (l == r) {       add(l, p + 8 * n, 0);       return;     }     int mid = (l + r) >> 1;     add((p << 1) + 8 * n, p + 8 * n, 0);     add((p << 1 | 1) + 8 * n, p + 8 * n, 0);     build_tree_two(p << 1, l, mid);     build_tree_two(p << 1 | 1, mid + 1, r);   }   void add_tree_one(int p, int l, int r, int x, int y, int dot,                     long long length) {     if (r < x || l > y) return;     if (l >= x && r <= y) {       add(dot, p + 4 * n, length);       return;     }     int mid = (l + r) >> 1;     add_tree_one(p << 1, l, mid, x, y, dot, length);     add_tree_one(p << 1 | 1, mid + 1, r, x, y, dot, length);   }   void add_tree_two(int p, int l, int r, int x, int y, int dot,                     long long length) {     if (r < x || l > y) return;     if (l >= x && r <= y) {       add(p + 8 * n, dot, length);       return;     }     int mid = (l + r) >> 1;     add_tree_two(p << 1, l, mid, x, y, dot, length);     add_tree_two(p << 1 | 1, mid + 1, r, x, y, dot, length);   }   long long dis[MAX];   bool vis[MAX];   struct point {     int dot;     long long length;   };   bool operator<(point a, point b) { return a.length > b.length; }   void dijkstra() {     priority_queue<point> list1;     dis[s] = 0;     list1.push({s, 0});     while (!list1.empty()) {       point now = list1.top();       list1.pop();       if (vis[now.dot]) continue;       vis[now.dot] = true;       for (int num = first[now.dot]; num != -1; num = nextt[num]) {         if (dis[v[num]] > dis[now.dot] + w[num]) {           dis[v[num]] = dis[now.dot] + w[num];           list1.push({v[num], dis[v[num]]});         }       }     }   }   void solve() {     while (~scanf( %d%d%d , &n, &q, &s)) {       cnt = 0;       for (int i = 0; i < MAX; ++i) first[i] = -1, dis[i] = INF, vis[i] = false;       build_tree_one(1, 1, n);       build_tree_two(1, 1, n);       for (int i = 1; i <= q; ++i) {         int op;         scanf( %d , &op);         if (op == 1) {           int a, b;           long long c;           scanf( %d%d%lld , &a, &b, &c);           add(a, b, c);         } else if (op == 2) {           int a, l, r;           long long c;           scanf( %d%d%d%lld , &a, &l, &r, &c);           add_tree_one(1, 1, n, l, r, a, c);         } else {           int a, l, r;           long long c;           scanf( %d%d%d%lld , &a, &l, &r, &c);           add_tree_two(1, 1, n, l, r, a, c);         }       }       dijkstra();       for (int i = 1; i <= n; ++i)         printf( %lld%c , dis[i] == INF ? -1 : dis[i], i == n ?   n  :    );     }   }   int main(void) {     solve();     return 0;   }   