非常好的题目。
首先这道题的限制及其抽象，我们冷静地思考切入点。
首先我们看一下毫无引导作用的样例，虽然说是没啥用，但是启发我们去思考这样一个问题，我们每条边的边权是不是只会取到 \(L\) 或者 \(R\)？答案是肯定的。
然后我们考虑哪些边会取到 \(L\) 哪些会取到 \(R\)，也就是思考图的最终状态的套路，首先取到 \(L\) 的一定是跟最短路紧密相关，想到这一步我们不难发现，最终状态一定是有一条最短路径，经过的边全都是 \(L\) 边，除此之外其它边一定都是 \(R\) 边。
但是就算如此我们既无法保证选的路径就是最短路，也无法保证题目的限制。题目限制其实就是说不存在经过 \(k\) 的最短路。我们现在的目的是在满足限制的条件下找到一个合法的钦定的最短路，我们不妨写下合法的充要条件，就是对于路径中的任意两个点 \(u,v\)，满足 \(dis_L(u,v)<dis_R(u,k)+dis_R(k,v)\)。
另外不难发现我们只需要保证经过 \(k\) 的路径一定列于钦定的最短路就行了，至于钦定的最短路是不是真的最短路我们无需关心。
然后我们需要在这个条件下找到合法的路径。这边可以投机取巧，就是一般这种题都得是用类似 Dijskra 的算法求，但是我们还是认真寻找思路吧。
我们考虑如何化简这个条件，这个条件非常复杂，我们来寻找这个条件式子的性质。首先 \(dis_R(u,k)\) 这种东西我们已经预处理过了，\(dis_L(u,v)\) 代表的路径也是可以只经过最短路的，那么我们尝试把限制挂到 \(v\)，这边我们钦定从 \(u\) 开始，其实对 dp 很熟悉的同学已经看出来这个东西可以 dp 了，把式子移项得出 \(dis_R(k,v)>dis_L(u,v)-dis_R(u,k)\)，然而对于一条路径的前缀我们可以很容易求出右边的最大值，那么我们直接设 \(f(u)\) 表示以 \(u\) 为结尾的路径 \(dis_L(u,v)-dis_R(u,k)\) 的最大值，转移直接跑 Dijkstra，如果遇到 \(f(u)\ge dis_R(k,u)\) 的就直接扔掉。
当然官方题解对于这个式子转化成了一个更有意思的意义。
把图中结点想象成城市，你是一个小偷，\(1\) 为起点，\(n\) 为你的藏身处，\(k\) 为派出所，你经过公路 \(e\) 的时间为 \(L_e\)，老百姓和警察经过公路 \(e\) 的时间为 \(R_e\)，老百姓发现小偷就会跑开车去派出所通风报信，而愚蠢的警察每收到一个信息都会派警察到各个城市抓小偷，问小偷能否在被抓前赶到藏身处。
经验丰富的你到达每个城市都能计算出一个危险系数 \(x\)，这个就是刚刚我们说的 \(f(u)\)，小偷若经过 \(e\) 要从城市 \(u\) 到城市 \(v\)，危险系数的变化就变为 \(\max(x+L_e,-dis_R(k,v))\)，如果 \(x\ge dis_R(k,u)\) 就要被抓了，根据这个意义想必你已经不难找到寻找最佳的路径的方法了吧！
代码：
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i (l); i <= (r); ++ i)
#define rrp(i, l, r) for (int i (r); i >= (l); -- i)
#define eb emplace_back
using namespace std;
#define pii pair <int, int>
#define inf 1000000000
#define ls (p << 1)
#define rs (ls | 1)
constexpr int N = 4e5 + 5, M = 1e6, P = 998244353;
typedef unsigned long long ull;
inline int rd () {int x = 0, f = 1;char ch = getchar ();while (! isdigit (ch)) {if (ch == '-') f = -1;ch = getchar ();}while (isdigit (ch)) {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar ();}return x * f;
}
int qpow (int x, int y, int p = P) {int ret (1);for (; y; y >>= 1, x = x * x % p) if (y & 1) ret = ret * x % p;return ret;
}
int n, m, k;
class node {public:int v, l, r;
} ;
vector <node> e[N];
int dis[N], t[N];
priority_queue <pii> q;
bool vis[N];
void solve () {n = rd (), m = rd (), k = rd ();rep (i, 1, n) e[i].clear ();rep (i, 1, m) {int u (rd ()), v (rd ()), l (rd ()), r (rd ());e[u].eb ((node) {v, l, r});e[v].eb ((node) {u, l, r});}rep (i, 1, n) dis[i] = 1e16, vis[i] = 0;dis[k] = 0;q.push (pii (0, k));while (! q.empty ()) {int u (q.top ().second); q.pop ();if (vis[u]) continue;vis[u] = 1; for (auto p : e[u]) {int v (p.v), w (p.r);if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;q.push (pii (- dis[v], v)); }}}rep (i, 1, n) vis[i] = 0, t[i] = 1e16;t[1] = - dis[1];q.push (pii (dis[1], 1));while (! q.empty ()) {int u (q.top ().second); q.pop ();if (vis[u] || t[u] >= dis[u]) continue;vis[u] = 1;for (auto p : e[u]) {int v (p.v), w (p.l);if (t[v] > max (- dis[v], t[u] + w)) {t[v] = max (- dis[v], t[u] + w);q.push (pii (- t[v], v));}}}puts (t[n] >= dis[n] ? "NO" : "YES");
}
int32_t main () {// freopen ("1.in", "r", stdin);// freopen ("1.out", "w", stdout);for (int T (rd ()); T; -- T) solve ();
}