#include <bits/stdc++.h>   #pragma GCC optimize( O3 )   using namespace std;   const double EPS = 1e-8;   const int mod = 1e9 + 7;   const int N = 3e6 + 10;   const long long INF = 1e18;   long long power(long long x, long long y) {     long long t = 1;     while (y > 0) {       if (y % 2)         y -= 1, t = t * x % mod;       else         y /= 2, x = x * x % mod;     }     return t;   }   long long dis[N];   vector<pair<long long, long long> > G[N];   int n, s, q;   void make(int C, int s, int e) {     if (s == e) {       G[C + n].push_back(make_pair(s, 0));       G[s].push_back(make_pair(C + n + 6 * n, 0));       return;     }     int m = (s + e) >> 1;     make(C * 2, s, m);     make(C * 2 + 1, m + 1, e);     G[C + n].push_back(make_pair(C * 2 + n, 0));     G[C + n].push_back(make_pair(C * 2 + 1 + n, 0));     G[C * 2 + n + 6 * n].push_back(make_pair(C + n + 6 * n, 0));     G[C * 2 + 1 + n + 6 * n].push_back(make_pair(C + n + 6 * n, 0));   }   void upd1(int C, int S, int E, int s, int e, int v, int w) {     if (s > E || e < S) return;     if (s <= S && E <= e) {       G[v].push_back(make_pair(C + n, w));       return;     }     int m = (S + E) >> 1;     upd1(C * 2, S, m, s, e, v, w);     upd1(C * 2 + 1, m + 1, E, s, e, v, w);   }   void upd2(int C, int S, int E, int s, int e, int v, int w) {     if (s > E || e < S) return;     if (s <= S && E <= e) {       G[C + n + 6 * n].push_back(make_pair(v, w));       return;     }     int m = (S + E) >> 1;     upd2(C * 2, S, m, s, e, v, w);     upd2(C * 2 + 1, m + 1, E, s, e, v, w);   }   priority_queue<pair<long long, long long> > P;   int main() {     scanf( %d%d%d , &n, &q, &s);     s--;     make(1, 0, n - 1);     for (int i = 0; i < q; ++i) {       int c;       scanf( %d , &c);       if (c == 1) {         int v, u, w;         scanf( %d%d%d , &v, &u, &w);         v--;         u--;         G[v].push_back(make_pair(u, w));       } else if (c == 2) {         int v, l, r, w;         scanf( %d%d%d%d , &v, &l, &r, &w);         v--;         l--;         r--;         upd1(1, 0, n - 1, l, r, v, w);       } else {         int v, l, r, w;         scanf( %d%d%d%d , &v, &l, &r, &w);         v--;         l--;         r--;         upd2(1, 0, n - 1, l, r, v, w);       }     }     for (int i = 0; i < N; ++i) dis[i] = INF;     dis[s] = 0;     P.push(make_pair(0, s));     while (!P.empty()) {       pair<long long, long long> nx = P.top();       P.pop();       nx.first = -nx.first;       if (dis[nx.second] < nx.first) continue;       for (int i = 0; i < G[nx.second].size(); ++i) {         long long cst = nx.first + G[nx.second][i].second;         int v = G[nx.second][i].first;         if (dis[v] > cst) {           dis[v] = cst;           P.push(make_pair(-cst, v));         }       }     }     for (int i = 0; i < n; ++i) {       if (dis[i] >= INF) dis[i] = -1;       printf( %lld%c , dis[i], (i + 1 == n) ?   n  :    );     }     return 0;   }   