解法
制約に注目すると，\(N \leq 50, a_{i} \leq 50\) と小さいので， これを利用したい． 素直にDPを考えると， 小さい部分を状態に入れたい． \(a\) が小さいことので，お金を状態に入れた DPをしたい． そこで，dp : (vertex, 所持金) \(\rightarrow\) 時間 を考える．
まず，状態数を見積もる． 所持金の上界と下界はを求める． ある頂点に 2回訪れる可能性はあるが，2回目に訪れて両替したとすると， 1回目に訪れたときに両替したとみなしてよい． 他の頂点で両替しなかった場合，\(N\) に行くまでに最大 \(MS := (N-1)*max(a) \leq 2500\) かかるので，これが上界としてとれる． 下界としては 0で良い． これなら DPできそう．
実装
ダイクストラと同様にすればよい． DPをするグラフ \(\hat{G}\) 自体はサイクルがあるが， 最短から確定していくことで，\(\hat{G}\) における無駄な辺を削除して， サイクルが無い形で計算ができるため DPが可能．
同じ頂点で 2枚以上両替することもあるが， 1枚だけ遷移を書けば十分． 1枚の遷移を繰り返せば良いだけだから．
注意
Priority queue を使うので，データ構造に順序 \(<\) を入れておく． また，所持金がマイナスになる遷移は出来ないのと， 所持金が \(MS\) より多いときは，\(MS\) とみなして良い． 多く持っていても，最善を尽くした遷移では使わないから．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
struct Edge{
ll to, a,b;
Edge(){}
Edge(ll to, ll a, ll b): to(to), a(a), b(b){}
};
struct D{
ll t, m, v; // time, money, vx
D(){}
D(ll v, ll m, ll t): v(v), m(m), t(t){}
bool operator < (const D a) const {
return t > a.t;
}
};
int main() {
ll n,m,s;
cin >> n >> m >> s;
const ll MS = n*50 + 5;
chmin(s, MS);
rep(i,m){
ll x,y,a,b; cin >> x >> y >> a >> b;
--x,--y;
g[x].push_back(Edge(y,a,b));
g[y].push_back(Edge(x,a,b));
}
vll c(n), d(n);
rep(i,n){
cin >> c[i] >> d[i];
}
vvll dp(n, vll(MS+1, INFL));
priority_queue<D> q;
auto push = [&](ll v, ll s, ll t){
if(s < 0) return;
chmin(s, MS);
if(chmin(dp[v][s], t)){
q.push(D(v,s,t));
}
};
q.push(D(0,s,0));
while(q.size()){
D cu = q.top(); q.pop();
ll v = cu.v;
ll t = cu.t;
ll m = cu.m;
// move
for(auto e: g[v]){
push(e.to, m - e.a, t + e.b);
}
// exchange
push(v, m + c[v], t + d[v]);
}
srep(i,1,n){
ll ans = INFL;
rep(s,MS+1){
chmin(ans, dp[i][s]);
}
assert(ans < INFL);
cout << ans << endl;
}
return 0;
}
