#include <bits/stdc++.h> #define F first #define S second using namespace std; typedef long long ll; typedef pair<int, int> pii; int n, m, k; vector<pii> e[3][100005]; int d[3][100005]; struct cmp { bool operator()(pii &ax, pii &bx) { return ax.S > bx.S; } }; priority_queue<pii, vector<pii>, cmp> pq; void BFS(int s, int t) { for (int i = 1; i <= n; i++) d[t][i] = 1000000009; pq.push({ s, 0 }); d[t][s] = 0; while (!pq.empty()) { pii uw = pq.top(); pq.pop(); int u = uw.F, w = uw.S; if (d[t][u] != w) continue; for (pii v : e[t][u]) { if (d[t][v.F] > w + v.S) { d[t][v.F] = w + v.S; pq.push({ v.F, d[t][v.F] }); } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("in.inp", "r", stdin); // freopen("out.out", "w", stdout); cin >> n >> m >> k; for (int i = 1; i <= m; i++) { int u, v, a, b; cin >> u >> v >> a >> b; e[0][u].push_back({ v, b }); e[1][v].push_back({ u, b }); e[2][v].push_back({ u, a }); } BFS(1, 0); BFS(n, 1); BFS(k, 2); int res = INT_MAX; for (int i = 1; i <= n; i++) { if (d[0][i] + d[2][i] < 60) { res = min(res, d[0][i] + d[1][i]); } } cout << res; return 0; }