这道题他会卡spfa，不过据说加SLF优化后能过，但还是讲讲正解吧。
题中有很关键的一句，就是无向边都是正的，只有单向边可能会有负的。当把整个图缩点后，有向边只会连接在每一个联通块之间（因为图中没有环），而且缩点后的图一定是一个DAG，DAG的最短路就可以拓扑排序后直接求出最短路。
因此，对于每一个联通块内，我们可以dijkstra跑最短路：除了常规的更新以外，每一次跑的时候都要先把这个块内的所有点都放进优先队列中，因为有的点可能已经从别的联通块更新了。然后对于一条边u->v，如果u,v在一个联通块内，就正常更新，否则是更新dis[y]，不把他放进队列，而是把y所在的联通块的入度--，如果为0，就放进拓扑序的队列中。
直到拓扑序的队列空。
对于有些走不到的点，可能在INF上加上了一个负数，因此最后判断是否能走到不能dis[i] = INF?，我就是稍微把这个上界放小一点，但又大于最远的dis，于是判断dis[i] > INF / 2?。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 2.5e4 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n, r, p, s;
vector<int> v[maxn], c[maxn];
vector<int> blo[maxn]; int col[maxn], cnt = ;
void dfs(int now)
{
col[now] = cnt; blo[cnt].push_back(now);
for(int i = ; i < (int)v[now].size(); ++i)
if(!col[v[now][i]]) dfs(v[now][i]);
} int in[maxn];
queue<int> topo; #define pr pair<int, int>
#define mp make_pair
int dis[maxn];
bool inq[maxn];
void dijkstra(int bl)
{
Mem(inq);
priority_queue<pr, vector<pr>, greater<pr> > q;
for(int i = ; i < (int)blo[bl].size(); ++i) q.push(mp(dis[blo[bl][i]], blo[bl][i]));
while(!q.empty())
{
int now = q.top().second; q.pop();
if(inq[now]) continue;
inq[now] = ;
for(int i = ; i < (int)v[now].size(); ++i)
{
int to = v[now][i];
if(col[now] == col[to])
{
if(dis[to] > dis[now] + c[now][i])
{
dis[to] = dis[now] + c[now][i];
q.push(mp(dis[to], to));
}
}
else
{
if(dis[to] > dis[now] + c[now][i]) dis[to] = dis[now] + c[now][i];
if(!--in[col[to]]) topo.push(col[to]);
}
}
}
} int main()
{
n = read(); r = read(); p = read(); s = read();
for(int i = ; i <= r; ++i)
{
int x = read(), y = read(), co = read();
v[x].push_back(y); c[x].push_back(co);
v[y].push_back(x); c[y].push_back(co);
}
for(int i = ; i <= n; ++i) if(!col[i]) ++cnt, dfs(i);
for(int i = ; i <= p; ++i)
{
int x = read(), y = read(), co = read();
v[x].push_back(y); c[x].push_back(co);
if(col[x] != col[y]) in[col[y]]++;
}
for(int i = ; i <= cnt; ++i) if(!in[i]) topo.push(i);
for(int i = ; i <= n; ++i) dis[i] = INF; dis[s] = ;
while(!topo.empty()) dijkstra(topo.front()), topo.pop();
for(int i = ; i <= n; ++i) dis[i] > (INF >> ) ? printf("NO PATH\n") : (write(dis[i]), enter);
return ;
}