spfa也能过
只要在更新操作的时候使用双端队列即可
不过时间有点紧

#include <bits/stdc++.h>
#pragma GCC timilize(2)
using namespace std;
const int N = 2e5;
int t, r, p, s;
int ne[N], head[N], idx, ver[N], e[N];
const int inf = 0x3f3f3f3f;
void add(int u, int v, int w) {
  ver[idx] = v;
  e[idx] = w;
  ne[idx] = head[u];
  head[u] = idx;
  idx++;
}
deque<int> q;
bool st[N];
int dist[N];
void spfa(int s) {
  memset(dist, 0x3f, sizeof(dist));
  memset(st, 0, sizeof(st));
  dist[s] = 0;
  st[s] = 1;
  q.push_front(s);
  while (q.size()) {
    int x = q.front();
    q.pop_front();
    st[x] = 0;
    for (register int i = head[x]; i != -1; i = ne[i]) {
      int j = ver[i];
      if (dist[j] > dist[x] + e[i]) {
        dist[j] = dist[x] + e[i];
        if (st[j] == 0) {
          if (dist[j] > dist[q.front()])  //双端队列的优化
            q.push_back(j);               //大于加入队尾
          else
            q.push_front(j);  //否则加入队头
          st[j] = 1;
        }
      }
    }
  }
}
inline int read() {
  int x = 0;
  int f = 1;
  char ch;
  ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10, x = x + ch - '0';
    ch = getchar();
  }
  return x * f;
}

int main() {
  int a, b, c;
  memset(head, -1, sizeof(head));
  t = read();
  r = read();
  p = read();
  s = read();
  for (register int i = 1; i <= r; i++) {
    a = read();
    b = read();
    c = read();
    add(a, b, c);
    add(b, a, c);
  }
  for (register int i = 1; i <= p; i++) {
    a = read();
    b = read();
    c = read();
    add(a, b, c);
  }
  spfa(s);
  for (register int i = 1; i <= t; i++) {
    if (dist[i] > inf / 2)
      cout << "NO PATH" << endl;
    else
      cout << dist[i] << endl;
  }
  return 0;
}