def enq(a,x)
b = a[i=-1]
until b.frozen?
return a << x if x >= (a=b)[-1]
return a.unshift x if x <= a[0]
b = a[i = a.bsearch_index{|y| x < (y.frozen? ? y: y[0])}-1]
end if b && b=a
return a.insert i+1, x unless a[i+9]
i>0 ? a[i]=[b,x] : enq(a[i+=1].to_a,x) rescue a[i]=[x,a[i]]
end
def deq(a) r=a.pop; a.push *a.pop if !a[-1].frozen?; r end
NS = 6; NM = (1<<NS)-1
SS = 13;SM = (1<<SS)-1
F =-> {gets.split.map &:to_i}
N,M,S = F[]
V = Array.new N
E = V.map { [] }
M.times {
u,v,a,b = F[]
u -= 1; v -= 1
E[u] << [v,a,b]
E[v] << [u,a,b]
}
X = V.map { c,d = F[]; [d, [c,2500].min] }
R,Q = [], [[S,2500].min]
while R.size < N
t = deq Q
s = SM & t; t >>= SS
n = NM & t; t >>= NS
(v = V[n]&.&SM) ? (next if v>=s || v>2500) : R << [n,t]
V[n] = (t<<SS) + s
x = X[n]
enq Q, (t-x[0]<<NS+SS) + (n<<SS) + s+x[1]
E[n].each {|n,a,b| enq Q, (t-b<<NS+SS) + (n<<SS) + s-a if s >= a }
end
puts R.sort![1,N].map{|i,t| -t}