AtCoder Beginner Contest 164 - Two Currencies

There are N cities numbered 1 to N, connected by M railroads.
You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.
The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes.
You cannot use gold coins to pay the fare.
There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin.
The transaction takes D_i minutes for each gold coin you give.
You can exchange any number of gold coins at each exchange counter.
For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

-----Constraints-----
 - 2 \leq N \leq 50
 - N-1 \leq M \leq 100
 - 0 \leq S \leq 10^9
 - 1 \leq A_i \leq 50
 - 1 \leq B_i,C_i,D_i \leq 10^9
 - 1 \leq U_i < V_i \leq N
 - There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).
 - Each city t=2,...,N can be reached from City 1 with some number of railroads.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N

-----Output-----
For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

-----Sample Input-----
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

-----Sample Output-----
2
14

The railway network in this input is shown in the figure below.
In this figure, each city is labeled as follows:
 - The first line: the ID number i of the city (i for City i)
 - The second line: C_i / D_i
Similarly, each railroad is labeled as follows:
 - The first line: the ID number i of the railroad (i for the i-th railroad in input)
 - The second line: A_i / B_i

You can travel from City 1 to City 2 in 2 minutes, as follows:
 - Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.


You can travel from City 1 to City 3 in 14 minutes, as follows:
 - Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.
 - At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 6 minutes.
 - Use the 1-st railroad to move from City 2 to City 1 in 2 minutes.
 - Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Source: atcoder | Difficulty: MEDIUM


Solutions:
def main():
	from heapq import heappush, heappop
	INF = 1 << 60
	MX_AG = 2500
	(N, M, S) = map(int, input().split())
	S = min(S, MX_AG)
	g = tuple((set() for _ in range(N)))
	for _ in range(M):
		(u, v, a, b) = map(int, input().split())
		u -= 1
		v -= 1
		g[u].add((v, a, b))
		g[v].add((u, a, b))
	exchange = []
	for _ in range(N):
		(c, d) = map(int, input().split())
		exchange.append((c, d))
	h = [(0, S, 0)]
	time = [[INF] * (MX_AG + 1) for _ in range(N)]
	time[0][S] = 0
	while h:
		(t, ag, loc) = heappop(h)
		for (to, fare, dt) in g[loc]:
			n_Ag = ag - fare
			if n_Ag < 0:
				continue
			cf = time[to][n_Ag]
			n_time = t + dt
			if cf <= n_time:
				continue
			time[to][n_Ag] = n_time
			heappush(h, (n_time, n_Ag, to))
		e_time = t + exchange[loc][1]
		e_Ag = ag + exchange[loc][0]
		if e_Ag > MX_AG:
			continue
		cf = time[loc][e_Ag]
		if cf <= e_time:
			continue
		time[loc][e_Ag] = e_time
		heappush(h, (e_time, e_Ag, loc))
	ans = (min(time[to]) for to in range(1, N))
	print('\n'.join(map(str, ans)))
main()


import heapq
import sys
input = sys.stdin.readline

def dijkstra_heap(s):
	d = [float('inf')] * n
	used = [True] * n
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, e)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, [e[0] + d[v], e[1]])
	return d
(N, m, s) = map(int, input().split())
L = [list(map(int, input().split())) for i in range(m)]
L2 = [list(map(int, input().split())) for i in range(N)]
n = N * (50 * (N - 1) + 1)
edge = [[] for i in range(n)]
for i in range(m):
	for j in range(50 * (N - 1) + 1):
		if j >= L[i][2]:
			edge[L[i][0] - 1 + N * j].append([L[i][3], L[i][1] - 1 + N * (j - L[i][2])])
			edge[L[i][1] - 1 + N * j].append([L[i][3], L[i][0] - 1 + N * (j - L[i][2])])
for i in range(N):
	for j in range(50 * (N - 1)):
		edge[i + N * j].append([L2[i][1], i + N * min(50 * (N - 1), j + L2[i][0])])
ans = [[] for i in range(N)]
D = dijkstra_heap(min(50 * (N - 1), s) * N)
for i in range(len(D)):
	ans[i % N].append(D[i])
for i in range(1, N):
	print(min(ans[i]))


(n, m, s) = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]
g = [[] for _ in range(n)]
for (u, v, a, b) in uvab:
	(u, v) = (u - 1, v - 1)
	g[u].append([v, a, b])
	g[v].append([u, a, b])
from heapq import heappop, heappush
inf = float('inf')
maxs = 50 * m
ans = [[inf] * (maxs + 1) for _ in range(n)]
s = min(s, maxs)
todo = [[0, 0, s]]
ans[0][s] = 0
while todo:
	(t, v, ss) = heappop(todo)
	if ans[v][ss] < t:
		continue
	for (nv, na, nb) in g[v]:
		if na > ss:
			continue
		if ans[nv][ss - na] > t + nb:
			heappush(todo, [t + nb, nv, ss - na])
			ans[nv][ss - na] = t + nb
	(c, d) = cd[v]
	nss = min(ss + c, maxs)
	if ans[v][nss] > t + d:
		heappush(todo, [t + d, v, nss])
		ans[v][nss] = t + d
for i in range(1, n):
	print(min(ans[i]))


from heapq import heapify, heappush, heappop
(N, M, S) = map(int, input().split())
tmp = [list(map(int, input().split())) for _ in range(M)]
U = [0 for _ in range(M)]
V = [0 for _ in range(M)]
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
for i in range(M):
	U[i] = tmp[i][0] - 1
	V[i] = tmp[i][1] - 1
	A[i] = tmp[i][2]
	B[i] = tmp[i][3]
A_m = max(A)
S = min(N * A_m, S)
I = [[] for _ in range(N * (N * A_m + 1))]
for i in range(M):
	for j in range(A[i], N * A_m + 1):
		I[U[i] * (N * A_m + 1) + j].append((V[i] * (N * A_m + 1) + j - A[i], B[i]))
		I[V[i] * (N * A_m + 1) + j].append((U[i] * (N * A_m + 1) + j - A[i], B[i]))
for i in range(N):
	(C, D) = map(int, input().split())
	for j in range(N * A_m + 1):
		I[i * (N * A_m + 1) + j].append((i * (N * A_m + 1) + min(C + j, N * A_m), D))

def dijkstra(I):
	N = len(I)
	task = []
	visited = [0 for _ in range(N)]
	min_cost = [0 for _ in range(N)]
	cost = [10 ** 20 for _ in range(N)]
	prev_points = [0 for _ in range(N)]
	heappush(task, (0, S, -1))
	flag = 0
	while task:
		while task:
			(c, p, prev) = heappop(task)
			if visited[p] == 0:
				break
			if len(task) == 0:
				flag = 1
		if flag == 1:
			break
		visited[p] = 1
		min_cost[p] = c
		prev_points[p] = prev
		for (j, c_ad) in I[p]:
			if visited[j] == 1:
				continue
			cost_next = next_cost(I, p, j, c, c_ad)
			if cost[j] > cost_next:
				cost[j] = cost_next
				heappush(task, (cost_next, j, p))
	return (min_cost, prev_points)

def next_cost(I, p, j, c, c_ad):
	return c + c_ad
(min_cost, prev_points) = dijkstra(I)
for i in range(1, N):
	print(min(min_cost[i * (N * A_m + 1):(i + 1) * (N * A_m + 1)]))


import math
import queue
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	(n, m, s) = map(int, ipt().split())
	mac = 2500
	way = [[] for i in range(n + 1)]
	for _ in range(m):
		(u, v, a, b) = map(int, ipt().split())
		way[u].append((v, a, b))
		way[v].append((u, a, b))
	for i in range(1, n + 1):
		(c, d) = map(int, ipt().split())
		way[i].append((i, -c, d))
	ct = [[10 ** 18] * 2501 for i in range(n + 1)]
	ct[1][min(s, mac)] = 0
	hq = [(0, 1, min(s, mac))]
	while hq:
		(ti, pl, mo) = hpq.heappop(hq)
		for (dp, dm, dt) in way[pl]:
			if mo >= dm and ct[dp][min(mo - dm, mac)] > ti + dt:
				ct[dp][min(mo - dm, mac)] = ti + dt
				hpq.heappush(hq, (ti + dt, dp, min(mo - dm, mac)))
	ans = [min(i) for i in ct[2:]]
	for i in ans:
		print(i)
	return
main()


from collections import defaultdict
import heapq as hq
(n, m, s) = map(int, input().split())
edges = [[] for _ in range(n + 1)]
INF = float('inf')
limit = 0
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	edges[u].append((v, a, b))
	edges[v].append((u, a, b))
	limit += a
if s > limit:
	s = limit
exchanges = [0]
for i in range(n):
	(c, d) = map(int, input().split())
	exchanges.append((c, d))
dp = [[INF] * (limit + 1) for _ in range(n + 1)]
q = []
hq.heapify(q)
hq.heappush(q, (0, 1, s))
dp[1][s] = 0
while q:
	(time, place, silver) = hq.heappop(q)
	(c, d) = exchanges[place]
	if silver + c <= limit:
		if time + d < dp[place][silver + c]:
			dp[place][silver + c] = time + d
			hq.heappush(q, (time + d, place, silver + c))
	elif time + d < dp[place][limit]:
		dp[place][limit] = time + d
		hq.heappush(q, (time + d, place, limit))
	for (v, a, b) in edges[place]:
		if silver - a >= 0 and dp[v][silver - a] > time + b:
			dp[v][silver - a] = time + b
			hq.heappush(q, (time + b, v, silver - a))
for i in dp[2:]:
	print(min(i))


import heapq

def Dijkstra(edge, start):
	d = [float('inf')] * (n * (A + 1))
	d[start] = 0
	pq = [(0, start)]
	heapq.heapify(pq)
	while pq:
		(dist, p) = heapq.heappop(pq)
		for (to, cost) in edge[p].items():
			if d[to] <= dist + cost:
				continue
			d[to] = dist + cost
			heapq.heappush(pq, (d[to], to))
	return d
(n, m, s) = map(int, input().split())
edge = [{} for _ in range(n)]
A = 2500
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	edge[u][v] = (a, b)
	edge[v][u] = (a, b)
A *= 2
C = [0] * n
D = [0] * n
for i in range(n):
	(C[i], D[i]) = map(int, input().split())
path = [{} for _ in range(n * (A + 1))]
for i in range(n):
	for j in range(A + 1):
		for (to, (a, b)) in edge[i].items():
			if j - a >= 0:
				path[i * (A + 1) + j][to * (A + 1) + j - a] = b
		path[i * (A + 1) + j][i * (A + 1) + min(j + C[i], A)] = D[i]
ans = Dijkstra(path, min(s, A))
for i in range(1, n):
	print(min(ans[i * (A + 1):i * (A + 1) + A + 1]))


import sys, math, copy, queue, itertools, bisect, collections
from heapq import *
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
INF = 10 ** 15
(N, M, S) = LI()
if S > N * 50:
	S = N * 50
root = [[] for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = LI()
	root[u - 1].append((v - 1, a, b))
	root[v - 1].append((u - 1, a, b))
city = [LI() for _ in range(N)]
dp = [[INF] * (N * 50 + 1) for _ in range(N)]
dp[0][S] = 0
hq = [[0, 0, S]]
heapify(hq)
while hq:
	(tm, pos, coin) = heappop(hq)
	c = coin
	t = tm
	if c < N * 50:
		c += city[pos][0]
		c = min(c, N * 50)
		t += city[pos][1]
		if dp[pos][c] > t:
			dp[pos][c] = t
			heappush(hq, [t, pos, c])
	for (p, a, b) in root[pos]:
		c = coin - a
		if c >= 0:
			if dp[p][c] > tm + b:
				dp[p][c] = tm + b
				heappush(hq, [tm + b, p, c])
for i in range(1, N):
	print(min(dp[i]))


(N, M, S) = map(int, input().split())
from heapq import heappop, heappush
inf = float('inf')
cost = [[] for _ in range(N)]
exc = []
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	cost[u].append((v, a, b))
	cost[v].append((u, a, b))
for _ in range(N):
	(c, d) = map(int, input().split())
	exc.append((c, d))
di = [inf] * 2451 * N
if S > 2450:
	S = 2450
di[S] = 0
hq = [(0, S)]
while hq:
	(t, v) = heappop(hq)
	u = v // 2451
	s = v % 2451
	for (x, a, b) in cost[u]:
		if s >= a:
			v_new = x * 2451 + s - a
			t_new = t + b
			if t_new < di[v_new]:
				di[v_new] = t_new
				heappush(hq, (t_new, v_new))
	(c, d) = exc[u]
	if s + c > 2450:
		c = 2450 - s
	v_new = v + c
	t_new = t + d
	if t_new < di[v_new]:
		di[v_new] = t_new
		heappush(hq, (t_new, v_new))
for i in range(1, N):
	m = di[i * 2451]
	for j in range(1, 2451):
		m = min(m, di[i * 2451 + j])
	print(m)


import sys
from heapq import heapify, heappop, heappush

def solve():
	input = sys.stdin.readline
	(N, M, S) = map(int, input().split())
	Edge = [[] for _ in range(N)]
	maxCost = 0
	for _ in range(M):
		(u, v, a, b) = map(int, input().split())
		Edge[u - 1].append((b, v - 1, a))
		Edge[v - 1].append((b, u - 1, a))
		maxCost = max(a, maxCost)
	exchange = [None] * N
	for i in range(N):
		exchange[i] = [int(c) for c in input().split()]
	maxCost *= N
	minTime = [[10 ** 20 for _ in range(maxCost + 1)] for i in range(N)]
	q = []
	heapify(q)
	heappush(q, (0, 0, S))
	while q:
		(cT, cN, cM) = heappop(q)
		if minTime[cN][min(maxCost, cM)] == 10 ** 20:
			minTime[cN][min(maxCost, cM)] = cT
			if cM < maxCost:
				heappush(q, (cT + exchange[cN][1], cN, cM + exchange[cN][0]))
			for (addTime, nextNode, payCost) in Edge[cN]:
				if cM >= payCost:
					heappush(q, (cT + addTime, nextNode, cM - payCost))
	for i in range(1, N):
		print(min(minTime[i]))
	return 0
solve()


from heapq import heappush, heappop
(N, M, S) = map(int, input().split())
mxCost = 0
edges = [[] for _ in range(N)]
for _ in range(M):
	(fr, to, cost, dist) = map(int, input().split())
	mxCost = max(mxCost, cost)
	fr -= 1
	to -= 1
	edges[fr].append((to, dist, cost))
	edges[to].append((fr, dist, cost))
for i in range(N):
	(C, D) = map(int, input().split())
	edges[i].append((i, D, -C))
que = [(0, S, 0)]
mxCost *= N - 1
minDsit = [[10 ** 18] * (mxCost + 1) for _ in range(N)]
minDsit[0][0] = 0
while que:
	(dist, s, now) = heappop(que)
	for (to, d, c) in edges[now]:
		cost = min(mxCost, s - c)
		if cost < 0 or minDsit[to][cost] <= dist + d:
			continue
		minDsit[to][cost] = dist + d
		heappush(que, (dist + d, cost, to))
for dist in minDsit[1:]:
	print(min(dist))


import heapq

def main():
	(N, M, S) = map(int, input().split())
	AB = [[] for _ in range(N)]
	maxA = 0
	for _ in range(M):
		(u, v, a, b) = map(int, input().split())
		AB[u - 1].append((a, b, v - 1))
		AB[v - 1].append((a, b, u - 1))
		maxA = max(maxA, a)
	for i in range(N):
		AB[i].sort()
	CD = [tuple(map(int, input().split())) for _ in range(N)]
	maxS = N * maxA
	cur = [(0, 0, S)]
	T = [-1] * N
	tc = N
	P = [-1] * N
	while tc:
		(t, u, s) = heapq.heappop(cur)
		if s <= P[u]:
			continue
		P[u] = s
		if T[u] == -1:
			T[u] = t
			tc -= 1
		for (a, b, v) in AB[u]:
			if s < a:
				break
			if P[v] < s - a:
				heapq.heappush(cur, (t + b, v, s - a))
		if s != maxS:
			(c, d) = CD[u]
			min_a = AB[u][0][0]
			k = max(1, (min_a - s + c - 1) // c)
			heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))
	print('\n'.join(map(str, T[1:])))
main()


def dijkstra(v, G):
	import heapq
	ret = [10 ** 20] * len(G)
	ret[v] = 0
	q = [(ret[i], i) for i in range(len(G))]
	heapq.heapify(q)
	while len(q):
		(tmpr, u) = heapq.heappop(q)
		if tmpr == ret[u]:
			for (w, l) in G[u]:
				if ret[w] > ret[u] + l:
					ret[w] = ret[u] + l
					heapq.heappush(q, (ret[w], w))
	return ret
(N, M, S) = map(int, input().split())
UVAB = [tuple(map(int, input().split())) for _ in range(M)]
CD = [tuple(map(int, input().split())) for _ in range(N)]
maxA = max([a for (u, v, a, b) in UVAB])
Q = maxA * (N - 1) + 1
G = [[] for _ in range(Q * N)]
for (u, v, a, b) in UVAB:
	for q in range(Q):
		if q >= a:
			G[Q * (u - 1) + q].append((Q * (v - 1) + q - a, b))
			G[Q * (v - 1) + q].append((Q * (u - 1) + q - a, b))
for (n, (c, d)) in enumerate(CD):
	for q in range(Q):
		G[Q * n + q].append((Q * n + min(Q - 1, c + q), d))
ans = dijkstra(min(S, Q - 1), G)
for n in range(1, N):
	print(min(ans[Q * n:Q * (n + 1)]))


(n, m, s) = map(int, input().split())
adj = [[] for i in range(n)]
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	adj[u - 1].append((v - 1, -a, b))
	adj[v - 1].append((u - 1, -a, b))
for i in range(n):
	(c, d) = map(int, input().split())
	adj[i].append((i, c, d))
out = [-1] * n
count = 0
LARGE = 50 * n
done = dict()
from heapq import *
q = []
if s > LARGE:
	s = LARGE
heappush(q, (0, 0, s))
while q:
	(time, loc, curr) = heappop(q)
	if out[loc] == -1:
		out[loc] = time
		count += 1
		if count == n:
			break
	for (nex, cost, timeD) in adj[loc]:
		currNex = curr + cost
		timeNex = time + timeD
		if currNex > LARGE:
			currNex = LARGE
		if currNex < 0:
			continue
		if (nex, currNex) not in done or timeNex < done[nex, currNex]:
			done[nex, currNex] = timeNex
			heappush(q, (timeNex, nex, currNex))
print(*out[1:], sep='\n')


from heapq import heappop, heappush
INF = float('inf')
(N, M, S) = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	(U, V, A, B) = map(int, input().split())
	graph[U - 1].append((V - 1, A, B))
	graph[V - 1].append((U - 1, A, B))
(C, D) = ([0] * N, [0] * N)
for i in range(N):
	(c, d) = map(int, input().split())
	(C[i], D[i]) = (c, d)

def Extdijkstra(start):
	nonlocal S
	N_d = len(graph)
	M = 2500
	if S >= M:
		S = M - 1
	dist = [[INF] * M for _ in range(N_d)]
	dist[start][S] = 0
	q = [(0, S, start)]
	while q:
		(d, num, v) = heappop(q)
		if num + C[v] < M and d + D[v] < dist[v][num + C[v]]:
			dist[v][num + C[v]] = d + D[v]
			heappush(q, (d + D[v], num + C[v], v))
		for (node, c, t) in graph[v]:
			if num >= c and d + t < dist[node][num - c]:
				dist[node][num - c] = d + t
				heappush(q, (d + t, num - c, node))
	return dist
d = Extdijkstra(0)
for i in range(1, N):
	print(min(d[i]))


from heapq import heappop, heappush
import sys
input = sys.stdin.readline
INF = 10 ** 100
MAX = 2500
(N, M, S) = map(int, input().split())
S = min(S, MAX)
G = [[] for _ in [0] * N]
C = []
for _ in [0] * M:
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	G[v].append((u, a, b))
	G[u].append((v, a, b))
for i in range(N):
	(a, b) = map(int, input().split())
	C.append((a, b))
dp = [[INF] * MAX for _ in [0] * N]
q = []

def push(t, s, v):
	if s < 0:
		return
	if s >= MAX:
		s = MAX - 1
	if dp[v][s] <= t:
		return
	dp[v][s] = t
	heappush(q, (t, s, v))
push(0, S, 0)
while q:
	(t, s, v) = heappop(q)
	if dp[v][s] != t:
		continue
	(c, d) = C[v]
	push(t + d, s + c, v)
	for (u, a, b) in G[v]:
		push(t + b, s - a, u)
for d in dp[1:]:
	ans = INF
	for s in range(MAX):
		if ans > d[s]:
			ans = d[s]
	print(ans)


from heapq import heappop, heappush, heapify

def main():
	(N, M, S) = map(int, input().split())
	S = min(S, 2500)
	edge = [[] for _ in range(N)]
	for _ in range(M):
		(U, V, A, B) = map(int, input().split())
		U -= 1
		V -= 1
		edge[U].append((V, A, B))
		edge[V].append((U, A, B))
	exchange = []
	for _ in range(N):
		(C, D) = map(int, input().split())
		exchange.append((C, D))
	dp = [[float('inf')] * 2510 for _ in range(N)]
	dp[0][S] = 0
	q = [(0, 0, S)]
	while q:
		(dist, v, money) = heappop(q)
		if dp[v][money] < dist:
			continue
		for (nv, fare, cost) in edge[v]:
			nm = money - fare
			if nm < 0:
				continue
			if dp[nv][nm] > dp[v][money] + cost:
				dp[nv][nm] = dp[v][money] + cost
				heappush(q, (dp[nv][nm], nv, nm))
		nm = min(money + exchange[v][0], 2500)
		if dp[v][nm] > dp[v][money] + exchange[v][1]:
			dp[v][nm] = dp[v][money] + exchange[v][1]
			heappush(q, (dp[v][nm], v, nm))
	for i in range(1, N):
		print(min(dp[i]))
main()


import sys
import heapq
input = sys.stdin.readline
NCOSTS = 2501
TIME_MAX = 10 ** 15
(N, M, S) = map(int, input().split())
adj = [[] for _ in range(N * NCOSTS)]
fare_adj = [[NCOSTS] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0

def node(city, silvers):
	return silvers * N + city
for i in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for j in range(a, NCOSTS):
		adj[node(u, j)].append((node(v, j - a), b))
		adj[node(v, j)].append((node(u, j - a), b))
for i in range(N):
	(c, d) = map(int, input().split())
	for j in range(NCOSTS - c):
		adj[node(i, j)].append((node(i, j + c), d))
mintime = [TIME_MAX for _ in range(N * NCOSTS)]

def search():
	q = [(0, node(0, min(S, NCOSTS - 1)))]
	while q:
		(t, node1) = heapq.heappop(q)
		if t > mintime[node1]:
			continue
		for (node2, cost) in adj[node1]:
			ntime = t + cost
			if mintime[node2] > ntime:
				mintime[node2] = ntime
				heapq.heappush(q, (ntime, node2))
search()
for i in range(1, N):
	print(min((mintime[node(i, j)] for j in range(NCOSTS))))


from collections import defaultdict
import heapq
(N, M, S) = list(map(int, input().split()))
E = [list(map(int, input().split())) for _ in range(M)]
C = [list(map(int, input().split())) for _ in range(N)]
A_max = max([a for (_, _, a, _) in E]) * N
D = defaultdict(lambda : [])
for (u, v, a, b) in E:
	u -= 1
	v -= 1
	for from_a in range(A_max + 1):
		if from_a - a < 0:
			continue
		from_state_u = (u, from_a)
		to_state_v = (v, from_a - a)
		D[from_state_u].append((b, to_state_v))
		from_state_v = (v, from_a)
		to_state_u = (u, from_a - a)
		D[from_state_v].append((b, to_state_u))
for (n, [c, d]) in enumerate(C):
	for a in range(A_max + 1):
		a_after = min(A_max, a + c)
		from_state = (n, a)
		to_state = (n, a_after)
		D[from_state].append((d, to_state))
start = (0, min(A_max, S))
Q = [(0, start)]
Dist = defaultdict(lambda : float('inf'))
Dist[start] = 0
while Q:
	q = heapq.heappop(Q)
	(cur_time, cur_state) = q
	if Dist[cur_state] < cur_time:
		continue
	for (cost, next_state) in D[cur_state]:
		next_time = cost + cur_time
		if Dist[next_state] > next_time:
			Dist[next_state] = next_time
			heapq.heappush(Q, (next_time, next_state))
for dest in range(1, N):
	ans = float('inf')
	for a in range(A_max + 1):
		state = (dest, a)
		ans = min(ans, Dist[state])
	print(ans)


from heapq import heappop, heappush

def solve():
	(n, m, s) = list(map(int, input().split()))
	graph = [[] for _ in range(n)]
	for _ in range(m):
		(u, v, a, b) = list(map(int, input().split()))
		graph[u - 1].append([v - 1, a, b])
		graph[v - 1].append([u - 1, a, b])
	ce = [[int(i) for i in input().split()] for _ in range(n)]
	maxSilver = 50 * 49
	inf = float('inf')
	ns_map = [[inf] * (maxSilver + 1) for _ in range(n)]
	q = [[0, 0, min(maxSilver, s)]]
	ns_map[0][min(maxSilver, s)] = 0
	while q:
		(ti, ni, si) = heappop(q)
		for g in graph[ni]:
			(n2, ai, bi) = g
			if si >= ai and ns_map[n2][si - ai] > ti + bi:
				ns_map[n2][si - ai] = ti + bi
				heappush(q, [ti + bi, n2, si - ai])
		(ci, di) = ce[ni]
		ti += di
		si = min(si + ci, maxSilver)
		if ns_map[ni][si] > ti:
			ns_map[ni][si] = ti
			heappush(q, [ti, ni, si])
	for i in range(1, n):
		print(min(ns_map[i]))

def __starting_point():
	solve()
__starting_point()


import heapq
(N, M, S) = map(int, input().split())
Map = [[] for _ in range(N)]
Ans = [[float('inf')] * 2500 for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	Map[u].append((v, a, b))
	Map[v].append((u, a, b))
for i in range(N):
	(c, d) = map(int, input().split())
	Map[i].append((i, -c, d))
Q = []
heapq.heappush(Q, (0, 0, min(2499, S)))
Ans[0][min(2499, S)] = 0
while Q:
	(time, where, money) = heapq.heappop(Q)
	for (nex, cost, take) in Map[where]:
		if cost > money:
			continue
		if Ans[nex][min(2499, money - cost)] > time + take:
			Ans[nex][min(2499, money - cost)] = time + take
			heapq.heappush(Q, (time + take, nex, money - cost))
for a in Ans[1:]:
	print(min(a))


from heapq import heappop, heappush
import sys

def input():
	return sys.stdin.readline().strip()

def main():
	(N, M, S) = map(int, input().split())
	to = [{} for _ in range(N)]
	for _ in range(M):
		(u, v, a, b) = map(int, input().split())
		u -= 1
		v -= 1
		to[u][v] = (a, b)
		to[v][u] = (a, b)
	info = tuple((tuple(map(int, input().split())) for _ in range(N)))
	MAX_SILVER = 50 * (N - 1)
	INF = 10 ** 18
	visited = [[False] * (MAX_SILVER + 1) for _ in range(N)]
	cost = [[INF] * (MAX_SILVER + 1) for _ in range(N)]
	q = []
	S = min(S, MAX_SILVER)
	heappush(q, (0, 0, S))
	while q:
		(t, now, s) = heappop(q)
		if visited[now][s]:
			continue
		visited[now][s] = True
		cost[now][s] = t
		for (nv, (a, b)) in to[now].items():
			nt = t + b
			rest = s - a
			if rest >= 0:
				if cost[nv][rest] <= nt:
					continue
				heappush(q, (nt, nv, rest))
		(rate, time) = info[now]
		nt = t + time
		ns = min(s + rate, MAX_SILVER)
		if cost[now][ns] <= nt:
			continue
		heappush(q, (nt, now, ns))
	for i in range(1, N):
		print(min(cost[i]))

def __starting_point():
	main()
__starting_point()


from heapq import heappop, heappush

def main():
	(N, M, S) = map(int, input().split())
	G = [[] for _ in range(N)]
	for i in range(M):
		(U, V, A, B) = map(int, input().split())
		G[U - 1].append([V - 1, A, B])
		G[V - 1].append([U - 1, A, B])
	C = []
	D = []
	for _ in range(N):
		(c, d) = map(int, input().split())
		C.append(c)
		D.append(d)
	MaxMoney = 2500
	dp = [[float('inf') for __ in range(MaxMoney + 1)] for _ in range(N)]
	cost = 0
	money = min(S, MaxMoney)
	que = []
	heappush(que, (cost, 0, money))
	dp[0][money] = 0
	while len(que) > 0:
		(cost, node, money) = heappop(que)
		stop_money = min(money + C[node], MaxMoney)
		stop_cost = cost + D[node]
		if stop_cost < dp[node][stop_money]:
			dp[node][stop_money] = stop_cost
			heappush(que, (stop_cost, node, stop_money))
		for (to_node, to_money, to_cost) in G[node]:
			money_ = min(money - to_money, MaxMoney)
			if money_ < 0:
				continue
			cost_ = cost + to_cost
			if dp[to_node][money_] <= cost_:
				continue
			dp[to_node][money_] = cost_
			heappush(que, (cost_, to_node, money_))
	for i in range(1, N):
		print(min(dp[i]))

def __starting_point():
	main()
__starting_point()


import heapq
(N, M, init_silver) = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)
G = [[] for _ in range(N)]
for i in range(M):
	(u, v, silver_cost, time_cost) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	G[u].append([v, silver_cost, time_cost])
	G[v].append([u, silver_cost, time_cost])
(change_rate, change_cost) = ([], [])
for i in range(N):
	(rate, cost) = map(int, input().split())
	G[i].append([i, -rate, cost])
	change_rate.append(rate)
	change_cost.append(cost)
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0
hq = [(0, 0, init_silver)]
while hq:
	(time, node, silver) = heapq.heappop(hq)
	for (to, silver_cost, time_cost) in G[node]:
		remain_silver = min(silver - silver_cost, MAX_COST)
		if remain_silver < 0:
			continue
		dp_next_value = time + time_cost
		if dp[to][remain_silver] <= dp_next_value:
			continue
		dp[to][remain_silver] = dp_next_value
		heapq.heappush(hq, (dp_next_value, to, remain_silver))
print(*[min(d) for d in dp[1:]], sep='\n')


MOD = 10 ** 9 + 7
INF = 10 ** 13
import sys
sys.setrecursionlimit(100000000)
dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
from heapq import heapify, heappop, heappush

def dijkstra(G, s=0):
	n = len(G)
	dist = [INF] * n
	dist[s] = 0
	q = [(0, s)]
	heapify(q)
	while q:
		(d, v) = heappop(q)
		if dist[v] < d:
			continue
		for (e, cost) in G[v]:
			if dist[e] > dist[v] + cost:
				dist[e] = dist[v] + cost
				heappush(q, (dist[e], e))
	return dist

def main():
	(n, m, s) = map(int, input().split())
	MAXV = 2500 * n
	G = [[] for _ in range(MAXV)]
	for _ in range(m):
		(u, v, a, b) = map(int, input().split())
		u -= 1
		v -= 1
		for i in range(2500 - a):
			G[u * 2500 + i + a].append((v * 2500 + i, b))
			G[v * 2500 + i + a].append((u * 2500 + i, b))
	for i in range(n):
		(c, d) = map(int, input().split())
		for j in range(2500 - c):
			G[i * 2500 + j].append((i * 2500 + j + c, d))
	dist = dijkstra(G, min(s, 2499))
	for i in range(1, n):
		ans = min(dist[2500 * i:2500 * (i + 1)])
		print(ans)
main()


import heapq
(N, M, S) = map(int, input().split())
E = [[] for _ in range(N)]
A = [[0] * N for _ in range(N)]
B = [[0] * N for _ in range(N)]
for i in range(M):
	(U, V, a, b) = map(int, input().split())
	u = U - 1
	v = V - 1
	E[u].append(v)
	E[v].append(u)
	A[u][v] = A[v][u] = a
	B[u][v] = B[v][u] = b
C = []
D = []
for i in range(N):
	(c, d) = map(int, input().split())
	C.append(c)
	D.append(d)
M = 50 * N
T = [[-1] * M for _ in range(N)]
h = []
heapq.heappush(h, (0, 0, min(M - 1, S)))
while h:
	(dmin, inode, snode) = heapq.heappop(h)
	if T[inode][snode] != -1:
		continue
	T[inode][snode] = dmin
	for enode in E[inode]:
		a = A[inode][enode]
		b = B[inode][enode]
		esnode = snode - a
		if esnode < 0 or T[enode][esnode] != -1:
			continue
		heapq.heappush(h, (dmin + b, enode, esnode))
	c = C[inode]
	d = D[inode]
	snode_c = min(M - 1, snode + c)
	if T[inode][snode_c] != -1:
		continue
	heapq.heappush(h, (dmin + d, inode, snode_c))
for inode in range(1, N):
	print(min([x for x in T[inode] if x >= 0]))


import sys
from heapq import *
input = sys.stdin.readline

def main():
	(n, m, s) = list(map(int, input().split()))
	s = min(s, 2500)
	railway = [[] for _ in range(n)]
	for i in range(m):
		(u, v, a, b) = list(map(int, input().split()))
		railway[u - 1].append((v - 1, a, b))
		railway[v - 1].append((u - 1, a, b))
	exchange = [None] * n
	for i in range(n):
		exchange[i] = tuple(map(int, input().split()))
	judge = [(0, 0, s)]
	heapify(judge)
	time = [[-1] * 2501 for _ in range(n + 1)] * n
	while judge:
		(t, now, money) = heappop(judge)
		if time[now][money] == -1:
			time[now][money] = t
		elif time[now][money] <= t:
			continue
		else:
			time[now][money] = min(time[now][money], t)
		if money < 2500:
			(c, d) = exchange[now]
			if time[now][min(2500, money + c)] == -1:
				heappush(judge, (t + d, now, min(2500, money + c)))
		for (v, a, b) in railway[now]:
			if money - a < 0:
				continue
			if time[v][money - a] == -1:
				heappush(judge, (t + b, v, money - a))
	for i in range(1, n):
		print(min(time[i]))

def __starting_point():
	main()
__starting_point()


import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline
(N, M, S) = map(int, input().split())
S = min(S, 2500)
INF = 10 ** 18
time = [[INF] * 2501 for _ in range(N)]
way = [[] for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	way[u - 1].append((v - 1, a, b))
	way[v - 1].append((u - 1, a, b))
CD = [list(map(int, input().split())) for _ in range(N)]
q = [(0, 0, S)]
while q:
	(ti, city, cur) = heappop(q)
	for (nxt, a, b) in way[city]:
		if cur >= a:
			if time[nxt][cur - a] > ti + b:
				time[nxt][cur - a] = ti + b
				heappush(q, (ti + b, nxt, cur - a))
	(c, d) = CD[city]
	nc = min(2500, c + cur)
	nt = ti + d
	if nt < time[city][nc]:
		time[city][nc] = nt
		heappush(q, (nt, city, nc))
for i in range(1, N):
	print(min(time[i]))


import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import *

def dijkstra(sta):
	dist = [10 ** 18] * (N * 2510)
	dist[sta] = 0
	pq = []
	heappush(pq, (dist[sta], sta))
	while pq:
		(d, v) = heappop(pq)
		if dist[v] < d:
			continue
		for (nv, w) in G[v]:
			if dist[nv] > dist[v] + w:
				dist[nv] = dist[v] + w
				heappush(pq, (dist[nv], nv))
	return dist
(N, M, S) = map(int, input().split())
serial = [[0] * 2510 for _ in range(N)]
c = 0
for i in range(N):
	for j in range(2510):
		serial[i][j] = c
		c += 1
G = [[] for _ in range(N * 2510)]
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for i in range(a, 2510):
		G[serial[u][i]].append((serial[v][i - a], b))
		G[serial[v][i]].append((serial[u][i - a], b))
for i in range(N):
	(c, d) = map(int, input().split())
	for j in range(2510):
		if j + c < 2510:
			G[serial[i][j]].append((serial[i][j + c], d))
dist = dijkstra(serial[0][min(S, 2509)])
for i in range(1, N):
	ans_i = 10 ** 18
	for j in range(2510):
		ans_i = min(ans_i, dist[serial[i][j]])
	print(ans_i)


(N, M, S) = map(int, input().split())
edges = [[] for _ in range(2500 * 50 + 100)]

def indexer(city, coin):
	return 50 * coin + city
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for scoin in range(a, 2501):
		edges[indexer(u, scoin)].append((b, indexer(v, scoin - a)))
		edges[indexer(v, scoin)].append((b, indexer(u, scoin - a)))
for i in range(N):
	(c, d) = map(int, input().split())
	for scoin in range(c, 2501):
		edges[indexer(i, scoin - c)].append((d, indexer(i, scoin)))

def dijkstra(s, n, edges):
	import heapq
	INF = float('inf')
	d = [INF] * n
	d[s] = 0
	pq = [(0, s)]
	while len(pq):
		(c, v) = heapq.heappop(pq)
		if d[v] < c:
			continue
		for (v2nvcost, nv) in edges[v]:
			if c + v2nvcost < d[nv]:
				d[nv] = c + v2nvcost
				heapq.heappush(pq, (d[nv], nv))
	return d
d = dijkstra(indexer(0, min(2500, S)), 2500 * 50 + 100, edges)
for i in range(1, N):
	ans = float('inf')
	for j in range(2501):
		ans = min(ans, d[indexer(i, j)])
	print(ans)


(n, m, s) = map(int, input().split())
uvab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(n)]
graph = [[] for i in range((n + 1) * 2500 + 1)]
for (u2, v2, a, b) in uvab:
	for (u, v) in ((u2, v2), (v2, u2)):
		for i in range(u * 2500, u * 2500 + 2500):
			if i % 2500 >= a:
				graph[i].append((i + (v - u) * 2500 - a, b))
for i in range(n):
	(c, d) = cd[i]
	for j in range((i + 1) * 2500, (i + 2) * 2500 - 1):
		graph[j].append((min((i + 2) * 2500 - 1, j + c), d))
import heapq as hq
start = 2500 + min(s, 2499)
dist = [10 ** 18] * ((n + 1) * 2500 + 1)
dist[start] = 0
q = [(0, start)]
hq.heapify(q)
while q:
	(_, x) = hq.heappop(q)
	for (y, d) in graph[x]:
		if dist[y] > dist[x] + d:
			dist[y] = dist[x] + d
			hq.heappush(q, (dist[y], y))
for i in range(2, n + 1):
	print(min(dist[i * 2500:(i + 1) * 2500]))


import sys
from heapq import heapify, heappop, heappush
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(N, M, S) = lr()
limit = 2500
S = min(S, limit)
graph = [[] for _ in range((N + 1) * (limit + 1))]
for _ in range(M):
	(u, v, a, b) = lr()
	for x in range(a, limit + 1):
		graph[u * (limit + 1) + x].append((v * (limit + 1) + x - a, b))
		graph[v * (limit + 1) + x].append((u * (limit + 1) + x - a, b))
for i in range(N):
	i += 1
	(c, d) = lr()
	for x in range(limit - c + 1):
		graph[i * (limit + 1) + x].append((i * (limit + 1) + x + c, d))

def dijkstra(start):
	INF = 10 ** 15
	dist = [INF] * ((N + 1) * (limit + 1))
	dist[start] = 0
	que = [(0, start)]
	while que:
		(d, prev) = heappop(que)
		if dist[prev] < d:
			continue
		for (next, time) in graph[prev]:
			d1 = d + time
			if dist[next] > d1:
				dist[next] = d1
				heappush(que, (d1, next))
	return dist
dist = dijkstra(1 * (limit + 1) + S)
for i in range(2, N + 1):
	answer = min(dist[i * (limit + 1):(i + 1) * (limit + 1)])
	print(answer)


import sys
input = lambda : sys.stdin.readline().rstrip()
import heapq
from collections import defaultdict
h = []
heapq.heapify(h)
(n, m, s) = list(map(int, input().split()))
(a, b) = [[None] * m for _ in range(2)]
(c, d) = [[None] * n for _ in range(2)]
ns = defaultdict(set)
uv2e = {}
for i in range(m):
	(u, v, a[i], b[i]) = list(map(int, input().split()))
	ns[u - 1].add(v - 1)
	ns[v - 1].add(u - 1)
	uv2e[u - 1, v - 1] = i
	uv2e[v - 1, u - 1] = i
for i in range(n):
	(c[i], d[i]) = list(map(int, input().split()))
maxs = max(a) * (n - 1)
s = min(s, maxs)
state = (0, 0, s)
ans = [[None] * (maxs + 1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
	count += 1
	(dd, u, ss) = heapq.heappop(h)
	if ans[u][ss] is not None and ans[u][ss] <= dd:
		continue
	ans[u][ss] = dd
	for v in ns[u]:
		e = uv2e[u, v]
		if ss < a[e] or ans[v][ss - a[e]] is not None:
			continue
		heapq.heappush(h, (dd + b[e], v, ss - a[e]))
	if ss + c[u] <= maxs:
		heapq.heappush(h, (dd + d[u], u, ss + c[u]))
	elif ss < maxs:
		heapq.heappush(h, (dd + d[u], u, maxs))
for item in ans[1:]:
	print(min(item))


import heapq
import sys
from collections import defaultdict
readline = sys.stdin.readline
(n, m, s) = map(int, input().split())
ls = [[] for _ in range(n)]
ms = []
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	ls[u - 1].append((v - 1, a, b))
	ls[v - 1].append((u - 1, a, b))
for _ in range(n):
	(c, d) = map(int, input().split())
	ms.append((c, d))
visited = defaultdict(int)
ans = [-1] * n
count = 0
q = [(0, 0, s)]
while q:
	(t, i, s) = heapq.heappop(q)
	if visited[i, s]:
		continue
	visited[i, s] = 1
	if ans[i] == -1:
		ans[i] = t
		count += 1
		if count == n:
			break
	if s <= 2500:
		(tc, td) = ms[i]
		heapq.heappush(q, (t + td, i, s + tc))
	for (ni, a, b) in ls[i]:
		if not visited[ni, s - a] and s >= a:
			heapq.heappush(q, (t + b, ni, s - a))
for v in ans[1:]:
	print(v)


from heapq import *
(N, M, S) = tuple(map(int, input().split()))
T = [[10 ** 18 for _ in range(2451)] for _ in range(N)]
act = [[] for _ in range(N)]
for i in range(M):
	(U, V, A, B) = tuple(map(int, input().split()))
	U -= 1
	V -= 1
	act[U] += [(V, A, B)]
	act[V] += [(U, A, B)]
for i in range(N):
	(C, D) = tuple(map(int, input().split()))
	act[i] += [(i, -C, D)]
que = [(0, 0, S)]
while que:
	(currentT, n, coins) = heappop(que)
	for (m, cost, t) in act[n]:
		if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
			T[m][min(2450, coins - cost)] = currentT + t
			heappush(que, (currentT + t, m, min(2450, coins - cost)))
for i in range(1, N):
	print(min(T[i]))


from heapq import heappop, heappush
INF = 10 ** 18
(N, M, S) = list(map(int, input().split()))
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]

def solve(link):
	ans = {}
	lim = 50 * (N - 1)
	w = [[INF] * (lim + 1) for _ in range(N)]
	hq = [(0, 0, min(S, lim))]
	while hq:
		(t, v, s) = heappop(hq)
		if t > w[v][s]:
			continue
		if v not in ans:
			ans[v] = t
			if len(ans) == N:
				break
		if s < lim:
			(c, d) = CD[v]
			new_s = min(lim, s + c)
			new_t = t + d
			if new_t < w[v][new_s]:
				w[v][new_s] = new_t
				heappush(hq, (new_t, v, new_s))
		for (u, a, b) in link[v]:
			if s < a:
				continue
			new_s = s - a
			new_t = t + b
			if new_t < w[u][new_s]:
				w[u][new_s] = new_t
				heappush(hq, (new_t, u, new_s))
	return ans

def main():
	link = [[] for _ in range(N)]
	for (u, v, a, b) in UVAB:
		link[u - 1].append((v - 1, a, b))
		link[v - 1].append((u - 1, a, b))
	ans = solve(link)
	for i in range(1, N):
		print(ans[i])

def __starting_point():
	main()
__starting_point()


import heapq
inf = 10 ** 18

def dijkstra(s, n, G):
	dist = [inf] * n
	edges = []
	dist[s] = 0
	for e in G[s]:
		heapq.heappush(edges, e)
	while edges:
		(cost, v) = heapq.heappop(edges)
		if dist[v] != inf:
			continue
		dist[v] = cost
		for (c, nv) in G[v]:
			if dist[nv] == inf:
				heapq.heappush(edges, (cost + c, nv))
	return dist
mx = 5005
(n, m, s) = map(int, input().split())
g = [[] for _ in range(n * mx)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for j in range(mx):
		if j >= a:
			g[u * mx + j].append((b, v * mx + j - a))
			g[v * mx + j].append((b, u * mx + j - a))
for i in range(n):
	(c, d) = map(int, input().split())
	for j in range(mx - c):
		g[i * mx + j].append((d, i * mx + j + c))
dist = dijkstra(min(s, mx - 1), len(g), g)
for i in range(1, n):
	res = inf
	for j in range(mx):
		res = min(res, dist[i * mx + j])
	print(res)


import sys, heapq
input = sys.stdin.buffer.readline
(n, m, s) = map(int, input().split())
if s >= 2500:
	s = 2499
dg = 2500
INF = 10 ** 15
dist = [INF] * (n * dg)
edge = [[] for i in range(n)]
a = [0] * m
b = [0] * m
for i in range(m):
	(u, v, aa, bb) = map(int, input().split())
	a[i] = aa
	b[i] = bb
	edge[u - 1].append((i, v - 1))
	edge[v - 1].append((i, u - 1))
c = [0] * n
d = [0] * n
for i in range(n):
	(cc, dd) = map(int, input().split())
	c[i] = cc
	d[i] = dd
tank = [(0, s)]
nonused = [True] * (n * dg)
while tank:
	(tim, fr) = heapq.heappop(tank)
	if dist[fr] != INF:
		continue
	dist[fr] = tim
	(pos, mon) = divmod(fr, dg)
	for (idx, go) in edge[pos]:
		if mon >= a[idx] and dist[go * dg + mon - a[idx]] == INF:
			heapq.heappush(tank, (tim + b[idx], go * dg + mon - a[idx]))
	if mon + c[pos] < dg and dist[fr + c[pos]] == INF:
		heapq.heappush(tank, (tim + d[pos], fr + c[pos]))
for i in range(1, n):
	res = INF
	for j in range(dg):
		if dist[i * dg + j] < res:
			res = dist[i * dg + j]
	print(res)


import heapq as hq
(n, m, s) = list(map(int, input().split()))
G = [[] for _ in range(n)]
for i in range(m):
	(u, v, A, B) = list(map(int, input().split()))
	u -= 1
	v -= 1
	hq.heappush(G[u], (B, A, v))
	hq.heappush(G[v], (B, A, u))
c = [0] * n
d = [0] * n
for i in range(n):
	(C, D) = list(map(int, input().split()))
	c[i] = C
	d[i] = D
inf = 1 << 61
M = 50 * 51
if s > M:
	s = M - 1
dp = [[inf] * M for _ in range(n)]
cur = 0
dp[cur][s] = 0
que = [(0, s, 0)]
while que:
	(cd, cs, cur) = hq.heappop(que)
	C = c[cur]
	D = d[cur]
	if dp[cur][cs] < cd:
		continue
	if cs + C < M and cd + D < dp[cur][cs + C]:
		dp[cur][cs + C] = cd + D
		hq.heappush(que, (cd + D, cs + C, cur))
	for g in G[cur]:
		B = g[0]
		A = g[1]
		to = g[2]
		if cs >= A and B + cd < dp[to][cs - A]:
			dp[to][cs - A] = B + cd
			hq.heappush(que, (B + cd, cs - A, to))
for i in range(1, n):
	print(min(dp[i]))


import sys
import heapq

def input():
	return sys.stdin.readline().rstrip()
(n, m, s) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
maxcoin = 0
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	graph[u].append((v, a, b))
	graph[v].append((u, a, b))
	maxcoin += a
ryougae = [0, 0] * (n + 1)
for i in range(1, n + 1):
	(c, d) = map(int, input().split())
	ryougae[i] = [c, d]
mindist = [[10 ** 20] * (maxcoin + 1) for _ in range(n + 1)]
hq = []
heapq.heappush(hq, (0, 1, min(maxcoin, s)))
while hq:
	(minute, city, coin) = heapq.heappop(hq)
	if mindist[city][coin] != 10 ** 20:
		continue
	mindist[city][coin] = minute
	for (i, pay, length) in graph[city]:
		if coin >= pay:
			if mindist[i][coin - pay] != 10 ** 20:
				continue
			heapq.heappush(hq, (minute + length, i, coin - pay))
	if coin < maxcoin:
		kankin = min(maxcoin, ryougae[city][0] + coin)
		if mindist[city][kankin] != 10 ** 20:
			continue
		heapq.heappush(hq, (minute + ryougae[city][1], city, kankin))
for i in range(2, n + 1):
	print(min(mindist[i]))


import sys
input = sys.stdin.readline
from heapq import heappush, heappop
(N, M, S) = map(int, input().split())
STATE = 50 * N + 1
vec = [[] for _ in range(STATE * N)]
for _ in range(M):
	(U, V, A, B) = map(int, input().split())
	U -= 1
	V -= 1
	for silver in range(A, STATE):
		vec[STATE * U + silver].append((STATE * V + silver - A, B))
		vec[STATE * V + silver].append((STATE * U + silver - A, B))
for i in range(N):
	(C, D) = map(int, input().split())
	for silver in range(STATE - C):
		vec[STATE * i + silver].append((STATE * i + silver + C, D))
dist = [float('inf')] * (STATE * N)
S = min(S, STATE - 1)
dist[S] = 0
q = [(0, S)]
while q:
	(cc, cur) = heappop(q)
	for (nex, nc) in vec[cur]:
		if dist[nex] <= cc + nc:
			continue
		dist[nex] = cc + nc
		heappush(q, (cc + nc, nex))
for i in range(1, N):
	print(min(dist[STATE * i:STATE * (i + 1)]))


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, m, s) = list(map(int, input().split()))
cd = [None] * n
from collections import defaultdict
ns = defaultdict(set)
nns = defaultdict(set)
uvab = [None] * m
for i in range(m):
	(u, v, a, b) = list(map(int, input().split()))
	u -= 1
	v -= 1
	uvab[i] = (u, v, a, b)
	ns[u].add((a, b, v))
	ns[v].add((a, b, u))
for i in range(n):
	cd[i] = list(map(int, input().split()))
ms = max((item[2] for item in uvab)) * (n - 1)
for u in range(n):
	for ss in range(ms + 1):
		for (a, b, v) in ns[u]:
			if ss >= a:
				nns[u, ss].add((b, (v, ss - a)))
		(c, d) = cd[u]
		if ss + c <= ms:
			nns[u, ss].add((d, (u, ss + c)))
ns = nns

def dijkstra(start):
	import heapq
	vals = {}
	h = [(0, start)]
	vals[start] = 0
	while h:
		(val, u) = heapq.heappop(h)
		for (d, v) in ns[u]:
			if v not in vals or vals[v] > val + d:
				vals[v] = val + d
				heapq.heappush(h, (vals[v], v))
	return vals
s = min(s, ms)
vals = dijkstra((0, s))
ans = [None] * (n - 1)
for u in range(1, n):
	ans[u - 1] = min((vals[u, s] for s in range(ms + 1)))
write('\n'.join(map(str, ans)))


import heapq
(N, M, S) = map(int, input().split())
MAX_COST = 2500
S = min(S, MAX_COST)
G = [[] for _ in range(N)]
for i in range(M):
	(u, v, s, t) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	G[u].append([v, s, t])
	G[v].append([u, s, t])
(change_rate, change_cost) = ([], [])
for i in range(N):
	(rate, cost) = map(int, input().split())
	change_rate.append(rate)
	change_cost.append(cost)
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][S] = 0
pq = [(0, 0, S)]
while pq:
	(time, node, silver) = heapq.heappop(pq)
	next_silver = min(silver + change_rate[node], MAX_COST)
	next_time = time + change_cost[node]
	if next_time < dp[node][next_silver]:
		dp[node][next_silver] = next_time
		heapq.heappush(pq, (next_time, node, next_silver))
	for (nei, ns, nt) in G[node]:
		remain_silver = min(silver - ns, MAX_COST)
		if remain_silver < 0:
			continue
		next_time = time + nt
		if dp[nei][remain_silver] > next_time:
			dp[nei][remain_silver] = next_time
			heapq.heappush(pq, (next_time, nei, remain_silver))
for d in dp[1:]:
	print(min(d))


(n, m, s) = map(int, input().split())
s = min(s, 2500)
edge = [[] for i in range(n * 50 * 51)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	for j in range(a, 2501):
		edge[u - 1 + j * n].append((v - 1 + (j - a) * n, b))
		edge[v - 1 + j * n].append((u - 1 + (j - a) * n, b))
for i in range(n):
	(c, d) = map(int, input().split())
	for j in range(2501 - c):
		edge[i + j * n].append((i + (j + c) * n, d))
	for j in range(2500):
		edge[i + (j + 1) * n].append((i + j * n, 0))
s = s * n
from heapq import heappush, heappop, heapify
d = [float('inf') for i in range(n * 50 * 51)]
pq = []
d[s] = 0
heappush(pq, (0, s))
while pq:
	(dist, u) = heappop(pq)
	for (v, cost) in edge[u]:
		if d[v] <= dist + cost:
			continue
		d[v] = dist + cost
		heappush(pq, (d[v], v))
for i in range(1, n):
	print(d[i])


(N, M, S) = map(int, input().split())
graph = {(i, j): [] for i in range(1, 51) for j in range(2501)}
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	for i in range(a, 2501):
		graph[u, i].append((b, (v, i - a)))
		graph[v, i].append((b, (u, i - a)))
for i in range(N):
	(c, d) = map(int, input().split())
	for j in range(2501):
		graph[i + 1, j].append((d, (i + 1, min(2500, j + c))))
dist = {(i, j): float('inf') for i in range(1, 51) for j in range(2501)}
dist[1, min(2500, S)] = 0
pq = []
import heapq
heapq.heapify(pq)
heapq.heappush(pq, (0, (1, min(2500, S))))
while pq:
	(mini_dis, node) = heapq.heappop(pq)
	if dist[node] < mini_dis:
		continue
	for (w, point) in graph[node]:
		if dist[point] < w:
			continue
		newlen = dist[node] + w
		if newlen < dist[point]:
			heapq.heappush(pq, (newlen, point))
			dist[point] = newlen
for i in range(2, N + 1):
	ans = 10 ** 20
	for j in range(2501):
		ans = min(ans, dist[i, j])
	print(ans)


import heapq
from collections import defaultdict as dd
from bisect import bisect_left
(N, M, S) = map(int, input().split())
costs = dd(dict)
times = dd(dict)
MAX = 0
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	MAX += a
	costs[u][v] = costs[v][u] = a
	times[u][v] = times[v][u] = b
Cs = [0]
Ds = [0]
for _ in range(N):
	(c, d) = map(int, input().split())
	Cs.append(c)
	Ds.append(d)
thres = [[] for _ in range(N + 1)]
vals = [[] for _ in range(N + 1)]
q = []
heapq.heappush(q, (0, 1, S))
while q:
	if all(thres):
		break
	(c, i, m) = heapq.heappop(q)
	if thres[i] and thres[i][-1] >= m:
		continue
	thres[i].append(m)
	vals[i].append(c)
	for to in costs[i].keys():
		cost = costs[i][to]
		t = times[i][to]
		if m >= cost:
			heapq.heappush(q, (c + t, to, m - cost))
	if m < MAX:
		heapq.heappush(q, (c + Ds[i], i, m + Cs[i]))
for i in range(2, N + 1):
	print(vals[i][0])


import sys
input = sys.stdin.buffer.readline
from heapq import heappop, heappush, heapify
(N, M, S) = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	graph[u - 1].append((v - 1, a, b))
	graph[v - 1].append((u - 1, a, b))
cd = [tuple(map(int, input().split())) for _ in range(N)]
INF = 1e+18
S = min(S, 2500)
time = [[INF] * 2501 for _ in range(N)]
q = [(0, 0, S)]
heapify(q)
while q:
	(now_time, cur_city, cur_coin) = heappop(q)
	for (nxt_city, cost, dt) in graph[cur_city]:
		if cur_coin >= cost and time[nxt_city][cur_coin - cost] > now_time + dt:
			time[nxt_city][cur_coin - cost] = now_time + dt
			heappush(q, (now_time + dt, nxt_city, cur_coin - cost))
	(c, d) = cd[cur_city]
	new_coin = min(2500, cur_coin + c)
	nxt_time = now_time + d
	if nxt_time < time[cur_city][new_coin]:
		time[cur_city][new_coin] = nxt_time
		heappush(q, (nxt_time, cur_city, new_coin))
for i in range(1, N):
	print(min(time[i]))


import heapq
(N, M, S) = list(map(int, input().rstrip().split()))
UVAB_list = [list(map(int, input().rstrip().split())) for i in range(M)]
CD_list = [list(map(int, input().rstrip().split())) for i in range(N)]
max_money = 2500
S = min(max_money, S)
graph = [None] + [[] for _ in range(N)]
change = [None] + [() for _ in range(N)]
dp = [None] + [[float('inf')] * (max_money + 1) for _ in range(N)]
dp[1][S] = 0
for (u, v, a, b) in UVAB_list:
	graph[u].append((v, a, b))
	graph[v].append((u, a, b))
for (i, (c, d)) in enumerate(CD_list):
	change[i + 1] = (c, d)
heap = [(0, 1, S)]
while heap:
	(cur_time, cur_city, cur_mone) = heapq.heappop(heap)
	changed_money = cur_mone + change[cur_city][0]
	changed_time = cur_time + change[cur_city][1]
	if changed_money <= max_money and changed_time < dp[cur_city][changed_money]:
		dp[cur_city][changed_money] = changed_time
		heapq.heappush(heap, (changed_time, cur_city, changed_money))
	for (next_city, cost_coin, cost_time) in graph[cur_city]:
		next_time = cur_time + cost_time
		next_money = min(max_money, cur_mone - cost_coin)
		if cur_mone >= cost_coin and next_time < dp[next_city][next_money]:
			dp[next_city][next_money] = next_time
			heapq.heappush(heap, (next_time, next_city, next_money))
for row in dp[2:]:
	print(min(row))


import sys
stdin = sys.stdin
ns = lambda : stdin.readline().rstrip()
ni = lambda : int(stdin.readline().rstrip())
nm = lambda : map(int, stdin.readline().split())
nl = lambda : list(map(int, stdin.readline().split()))
(n, m, s) = nm()
N = n * 3001
G = [list() for _ in range(N)]
for _ in range(m):
	(u, v, a, b) = nm()
	u -= 1
	v -= 1
	for j in range(0, N, n):
		if v + j - a * n >= 0:
			G[u + j].append((v + j - a * n, b))
		if u + j - a * n >= 0:
			G[v + j].append((u + j - a * n, b))
for u in range(n):
	(c, d) = nm()
	for j in range(0, N, n):
		G[u + j].append((min(u + j + c * n, u + N - n), d))
import heapq as hq

def dijkstra(G, s, t=None):
	dist = [1 << 60] * len(G)
	dist[s] = 0
	q = [(0, s)]
	while q:
		(d, v) = hq.heappop(q)
		if d > dist[v]:
			continue
		for (x, c) in G[v]:
			if dist[x] > d + c:
				dist[x] = d + c
				hq.heappush(q, (d + c, x))
	if t is None:
		return dist
	else:
		return dist[t]
dist = dijkstra(G, min(s, 3000) * n)
for i in range(1, n):
	print(min(dist[i::n]))


def main():
	from heapq import heappush, heappop
	((n, m, s), *t) = [map(int, r.split()) for r in open(0)]
	e = [[] for _ in range(8 ** 6)]
	for (u, v, a, b) in t[:m]:
		for i in range(2501 - a):
			e[(i + a) * 51 + u] += ((b, i * 51 + v),)
			e[(i + a) * 51 + v] += ((b, i * 51 + u),)
	for (i, (c, d)) in enumerate(t[m:], 1):
		for j in range(2501 - c):
			e[j * 51 + i] += ((d, (j + c) * 51 + i),)
	x = [10 ** 18] * 8 ** 6
	f = [1] * 8 ** 6
	q = [(0, min(2500, s) * 51 + 1)]
	while q:
		(c, v) = heappop(q)
		if f[v] < 1:
			continue
		(x[v], f[v]) = (c, 0)
		for (p, w) in e[v]:
			if f[w]:
				heappush(q, (c + p, w))
	for i in range(2, n + 1):
		print(min(x[i::51]))
main()


import heapq
inf = 10 ** 20
h = 2500
(n, m, s) = map(int, input().split())
s = min(h - 1, s)
A = [[inf for j in range(n)] for i in range(n)]
B = [[inf for j in range(n)] for i in range(n)]
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	A[u - 1][v - 1] = a
	A[v - 1][u - 1] = a
	B[u - 1][v - 1] = b
	B[v - 1][u - 1] = b
CD = [tuple(map(int, input().split())) for i in range(n)]
C = [c for (c, d) in CD]
D = [d for (c, d) in CD]
G = {(i, x): {} for i in range(n) for x in range(h)}
for i in range(n):
	for j in range(n):
		for x in range(h):
			if i == j:
				G[i, x][i, x] = 0
				if x - 1 >= 0:
					G[i, x][i, x - 1] = 0
				if x + C[i] < h:
					G[i, x][i, x + C[i]] = D[i]
			elif x >= A[i][j]:
				G[i, x][j, x - A[i][j]] = B[i][j]
T = {(i, x): inf for i in range(n) for x in range(h)}
T[0, s] = 0
Q = [(0, (0, s))]
heapq.heapify(Q)
while Q:
	(_, (i, x)) = heapq.heappop(Q)
	for (j, y) in G[i, x].keys():
		if T[i, x] + G[i, x][j, y] < T[j, y]:
			T[j, y] = T[i, x] + G[i, x][j, y]
			heapq.heappush(Q, (T[j, y], (j, y)))
for i in range(1, n):
	print(T[i, 0])


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from heapq import heappop, heappush

def resolve():
	(n, m, s) = map(int, input().split())
	S = 0
	E = [[] for _ in range(n)]
	for _ in range(m):
		(u, v, a, b) = map(int, input().split())
		u -= 1
		v -= 1
		S += a
		E[u].append((v, -a, b))
		E[v].append((u, -a, b))
	for v in range(n):
		(c, d) = map(int, input().split())
		E[v].append((v, c, d))
	dist = [[INF] * (S + 1) for _ in range(n)]
	s = min(s, S)
	dist[0][s] = 0
	heap = [(0, 0, s)]
	while heap:
		(d, v, s) = heappop(heap)
		if dist[v][s] < d:
			continue
		for (nv, ds, dd) in E[v]:
			ns = s + ds
			if not 0 <= ns <= S:
				continue
			if dist[nv][ns] > dist[v][s] + dd:
				dist[nv][ns] = dist[v][s] + dd
				heappush(heap, (dist[nv][ns], nv, ns))
	for v in range(1, n):
		print(min((dist[v][s] for s in range(S + 1))))
resolve()


import sys
input = sys.stdin.buffer.readline
import heapq

def main():
	(N, M, S) = map(int, input().split())
	edge = [[] for _ in range(N)]
	for _ in range(M):
		(u, v, a, b) = map(int, input().split())
		edge[u - 1].append((v - 1, a, b))
		edge[v - 1].append((u - 1, a, b))
	change = [tuple(map(int, input().split())) for _ in range(N)]
	MAX_COST = 50 * 50
	S = min(S, MAX_COST)
	q = [(0, (0, S))]
	ans = [-1] * N
	visited = set()
	heapq.heapify(q)
	while q:
		(time, data) = heapq.heappop(q)
		(now, money) = data
		if ans[now] == -1:
			ans[now] = time
			if -1 not in ans:
				break
		if data in visited:
			continue
		visited.add(data)
		for (fol, a, b) in edge[now]:
			if money >= a:
				fol_data = (fol, money - a)
				if fol_data in visited:
					continue
				heapq.heappush(q, (time + b, fol_data))
		(c, d) = change[now]
		if money + c > MAX_COST:
			continue
		heapq.heappush(q, (time + d, (now, money + c)))
	print(*ans[1:], sep='\n')
main()


z = lambda i, c: i + c * 50
(n, m, s) = map(int, input().split())
e = [[] for _ in range(4 ** 9)]
from heapq import *
t = z(0, min(2500, s))
d = [9 ** 20] * 4 ** 9
d[t] = 0
h = [[0, t]]
q = [9 ** 20] * (n - 1)
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	for i in range(a, 2501):
		e[z(u - 1, i)].append((z(v - 1, i - a), b))
		e[z(v - 1, i)].append((z(u - 1, i - a), b))
for i in range(n):
	(c, r) = map(int, input().split())
	for j in range(c, 2501):
		e[z(i, j - c)].append((z(i, j), r))
while h:
	(c, v) = heappop(h)
	if d[v] < c:
		continue
	for (u, t) in e[v]:
		if c + t < d[u]:
			d[u] = c + t
			heappush(h, [c + t, u])
for i in range(n - 1):
	for j in range(2501):
		q[i] = min(q[i], d[z(i + 1, j)])
print(*q)


from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
phi = lambda city, silver: city * 2501 + silver
psi = lambda x: (x // 2501, x % 2501)
(n, m, s) = map(int, input().split())
g = [[] for _ in range(n * 2501 + 1)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	for j in range(2501):
		if j - a >= 0:
			g[phi(u - 1, j)].append((phi(v - 1, j - a), b))
			g[phi(v - 1, j)].append((phi(u - 1, j - a), b))
for i in range(n):
	(c, d) = map(int, input().split())
	for j in range(2501):
		if j + c <= 2500:
			g[phi(i, j)].append((phi(i, j + c), d))

def dijkstra(s, n, g):
	d = [10 ** 18] * n
	d[s] = 0
	q = [(0, s)]
	while q:
		(dist_u, u) = heappop(q)
		if d[u] < dist_u:
			continue
		for (v, c) in g[u]:
			if d[v] > dist_u + c:
				d[v] = dist_u + c
				heappush(q, (d[v], v))
	return d
s = min(s, 2500)
d = dijkstra(phi(0, s), n * 2501 + 1, g)
for i in range(1, n):
	print(min(d[phi(i, 0):phi(i + 1, 0)]))


import math
(n, m, s) = map(int, input().split())
road = []
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	road.append([u, v, a, b])
change = []
for i in range(n):
	(c, d) = map(int, input().split())
	change.append([c, d])
tree = [[] for _ in range(n + 1)]
for i in range(m):
	r = road[i]
	tree[r[0]].append([r[0], r[1], r[2], r[3]])
	tree[r[1]].append([r[1], r[0], r[2], r[3]])
least_cost = [[] for _ in range(n + 1)]
for l in range(n + 1):
	least_cost[l] = [math.inf] * 2501

def insort_queue(q, v):
	len_a = len(q)
	if len_a == 0:
		q.append(v)
		return
	min = 0
	max_1 = len_a
	if max_1 == 1:
		if v[2] > q[0][2]:
			min = 1
		else:
			min = 0
	while max_1 - min > 1:
		mid = (max_1 + min) // 2
		if v[2] > q[mid][2]:
			min = mid
		else:
			max_1 = mid
	index = max_1
	q.insert(index, v)
queue = []

def dijakstra(q):
	while q != []:
		hwd = q.pop(0)
		if least_cost[hwd[0]][hwd[1]] > hwd[2]:
			least_cost[hwd[0]][hwd[1]] = hwd[2]
			for node in tree[hwd[0]]:
				if hwd[1] - node[2] >= 0:
					insort_queue(q, [node[1], hwd[1] - node[2], hwd[2] + node[3]])
			if hwd[1] + change[hwd[0] - 1][0] <= 500:
				insort_queue(q, [hwd[0], hwd[1] + change[hwd[0] - 1][0], hwd[2] + change[hwd[0] - 1][1]])
	return least_cost
if s > 2500:
	s = 2500
queue.append([1, s, 0])
ans = dijakstra(queue)
for i in range(2, n + 1):
	print(min(ans[i]))


(n, m, s) = [int(i) for i in input().split()]
e = []
for _ in range(m):
	(u, v, a, b) = [int(i) for i in input().split()]
	u -= 1
	v -= 1
	e.append([u, v, a, b])
co = [[int(i) for i in input().split()] for _ in range(n)]
dp = [[10 ** 18] * 6000 for _ in range(n)]
dp[0][min(5999, s)] = 0
for i in range(6000):
	if i + co[0][0] < 6000:
		dp[0][i + co[0][0]] = min(dp[0][i + co[0][0]], dp[0][i] + co[0][1])
for _ in range(n):
	for (u, v, a, b) in e:
		for j in range(a, 6000):
			dp[v][j - a] = min(dp[v][j - a], dp[u][j] + b)
		for i in range(6000):
			if i + co[v][0] < 6000:
				dp[v][i + co[v][0]] = min(dp[v][i + co[v][0]], dp[v][i] + co[v][1])
		for j in range(a, 6000):
			dp[u][j - a] = min(dp[u][j - a], dp[v][j] + b)
		for i in range(6000):
			if i + co[u][0] < 6000:
				dp[u][i + co[u][0]] = min(dp[u][i + co[u][0]], dp[u][i] + co[u][1])
for i in range(1, n):
	print(min(dp[i]))


import heapq
(n, m, s) = [int(x) for x in input().split()]
adj = [[] for u in range(n + 1)]
for e in range(m):
	(u, v, a, b) = [int(x) for x in input().split()]
	adj[u].append((v, a, b))
	adj[v].append((u, a, b))
exchange = [[int(x) for x in input().split()] if u else [] for u in range(n + 1)]

def bound(s):
	return min(s, n * 50)
(pq, done, d) = ([(0, 1, bound(s))], set(), {(1, bound(s)): 0})
ans = [float('inf') for u in range(n + 1)]
while len(pq) > 0:
	(dist, u, s) = heapq.heappop(pq)
	ans[u] = min(ans[u], dist)
	if (u, s) not in done:
		for (v, a, b) in adj[u]:
			if s >= a and d.get((v, bound(s - a)), float('inf')) > d[u, s] + b:
				d[v, bound(s - a)] = d[u, s] + b
				heapq.heappush(pq, (d[v, bound(s - a)], v, bound(s - a)))
		(c, t) = exchange[u]
		if d.get((u, bound(s + c)), float('inf')) > d[u, s] + t:
			d[u, bound(s + c)] = d[u, s] + t
			heapq.heappush(pq, (d[u, bound(s + c)], u, bound(s + c)))
		done.add((u, s))
print(*(ans[u] for u in range(2, n + 1)), sep='\n')


import heapq

def dijkstra_heap():
	used = [-1] * (2451 * n)
	edgelist = []
	heapq.heappush(edgelist, [0, ss])
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if used[minedge[1]] != -1:
			continue
		v = minedge[1]
		kai = minedge[0]
		mai = v % 2451
		used[v] = kai
		for e in edge[v // 2451]:
			if mai - e[1] >= 0:
				sss = mai - e[1]
				if used[e[2] * 2451 + sss] == -1:
					heapq.heappush(edgelist, [e[0] + kai, e[2] * 2451 + sss])
		if mai + cd[v // 2451][0] <= 2450:
			if used[v + cd[v // 2451][0]] == -1:
				heapq.heappush(edgelist, [kai + cd[v // 2451][1], v + cd[v // 2451][0]])
	return used
(n, m, ss) = map(int, input().split())
ss = min(2450, ss)
edge = [[] for i in range(n)]
for i in range(m):
	(x, y, a, b) = map(int, input().split())
	edge[x - 1].append([b, a, y - 1])
	edge[y - 1].append([b, a, x - 1])
cd = []
for i in range(n):
	cd.append(list(map(int, input().split())))
pp = dijkstra_heap()
for i in range(1, n):
	ans = 10 ** 20
	for j in range(2451):
		if pp[i * 2451 + j] != -1:
			ans = min(ans, pp[i * 2451 + j])
	print(ans)


import collections
(n, m, s) = map(int, input().split())
g = [[] for _ in range(n + 1)]
dic = {}
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
	dic[u, v] = (a, b)
	dic[v, u] = (a, b)
arr = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)]
cost = [[10 ** 18] * 2501 for _ in range(n + 1)]
for i in range(min(2500, s) + 1):
	cost[1][i] = 0
q = collections.deque()
q.append(1)
while len(q) != 0:
	v = q.popleft()
	(c, d) = arr[v]
	for i in range(c, 2501):
		cost[v][i] = min(cost[v][i], cost[v][i - c] + d)
	for u in g[v]:
		(a, b) = dic[v, u]
		flag = False
		for i in range(a, 2501):
			if cost[u][i - a] > cost[v][i] + b:
				cost[u][i - a] = cost[v][i] + b
				flag = True
		if flag == True:
			q.append(u)
for i in range(2, n + 1):
	print(min(cost[i]))


ic = lambda i, c: i + c * 50
(n, m, s) = map(int, input().split())
edge = [[] for _ in range(125100)]
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for i in range(a, 2501):
		edge[ic(u, i)].append((ic(v, i - a), b))
		edge[ic(v, i)].append((ic(u, i - a), b))
for i in range(n):
	(c, d) = map(int, input().split())
	for j in range(c, 2501):
		edge[ic(i, j - c)].append((ic(i, j), d))
from heapq import heappop, heappush

def dijkstra(s, n, edge):
	inf = 10 ** 20
	ans = [inf] * n
	ans[s] = 0
	h = [[0, s]]
	while h:
		(c, v) = heappop(h)
		if ans[v] < c:
			continue
		for (u, t) in edge[v]:
			if c + t < ans[u]:
				ans[u] = c + t
				heappush(h, [c + t, u])
	return ans
d = dijkstra(ic(0, min(2500, s)), 125100, edge)
ans = [0] + [10 ** 20] * (n - 1)
for i in range(1, n):
	for j in range(2501):
		ans[i] = min(ans[i], d[ic(i, j)])
print(*ans[1:])


import heapq
from collections import defaultdict
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines
(n, m, s) = map(int, input().split())
connect = defaultdict(list)
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	connect[u].append((v, a, b))
	connect[v].append((u, a, b))
(c, d) = ([-1], [-1])
for i in range(n):
	(c_, d_) = map(int, input().split())
	c.append(c_)
	d.append(d_)
ans = [-1] * (n + 1)
dp = [{} for _ in range(n + 1)]
coin_max = [-1] * (n + 1)
h = [(0, s, 1)]
heapq.heapify(h)
while heapq:
	(t, coin, city) = heapq.heappop(h)
	if ans[city] == -1:
		ans[city] = t
		if all([v >= 0 for v in ans[2:]]):
			break
	if coin not in dp[city]:
		dp[city][coin] = t
	else:
		continue
	if coin_max[city] >= coin:
		continue
	else:
		coin_max[city] = coin
	for (neighbor, a, b) in connect[city]:
		if coin - a >= 0 and neighbor != city:
			if coin - a not in dp[neighbor]:
				heapq.heappush(h, (t + b, coin - a, neighbor))
	if coin + c[city] not in dp[city]:
		heapq.heappush(h, (t + d[city], coin + c[city], city))
print('\n'.join(map(str, ans[2:])))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
from collections import deque
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def main():
	(N, M, S) = LI()
	G = [[[] for _ in range(2501)] for _ in range(N)]
	for i in range(M):
		(u, v, a, b) = LI()
		u -= 1
		v -= 1
		for money in range(2501):
			if money - a < 0:
				continue
			G[u][money].append((b, v, money - a))
			G[v][money].append((b, u, money - a))
	for i in range(N):
		(c, d) = LI()
		for money in range(2501):
			new_money = min(2500, money + c)
			G[i][money].append((d, i, new_money))

	def dijkstra(u, s):
		q = []
		d = [[inf for __ in range(2501)] for _ in range(N)]
		visited = set()
		dist = 0
		money = min(2500, s)
		d[u][money] = dist
		heapq.heappush(q, (dist, u, money))
		while len(q) > 0:
			(dist, u, u_money) = heapq.heappop(q)
			if (u, u_money) in visited:
				continue
			visited.add((u, u_money))
			for next_node_tuple in G[u][u_money]:
				(cost, v, v_money) = next_node_tuple
				if dist + cost < d[v][v_money]:
					d[v][v_money] = dist + cost
					heapq.heappush(q, (d[v][v_money], v, v_money))
		return d
	d = dijkstra(0, S)
	for i in range(1, N):
		print(min(d[i]))
main()


def solve():
	import sys
	import heapq
	MAX_S = 50 * 50
	(N, M, S) = list(map(int, sys.stdin.readline().split()))
	graph = [[] for _ in range(N)]
	for _ in range(M):
		(u, v, a, b) = list(map(int, sys.stdin.readline().split()))
		(u, v) = (u - 1, v - 1)
		graph[u].append((v, a, b))
		graph[v].append((u, a, b))
	ryogae = []
	for _ in range(N):
		(c, d) = list(map(int, sys.stdin.readline().split()))
		ryogae.append((c, d))
	dp = [[float('inf') for _ in range(MAX_S + 1)] for __ in range(N)]
	s = min(S, MAX_S)
	que = []
	heapq.heappush(que, (0, 0, s))
	while len(que) != 0:
		(t, v, s) = heapq.heappop(que)
		(c, d) = ryogae[v]
		ns = min(s + c, MAX_S)
		if dp[v][ns] > t + d:
			dp[v][ns] = t + d
			heapq.heappush(que, (t + d, v, ns))
		for (u, a, b) in graph[v]:
			if s - a < 0:
				continue
			if dp[u][s - a] > t + b:
				dp[u][s - a] = t + b
				heapq.heappush(que, (t + b, u, s - a))
	for v in range(1, N):
		ans = float('inf')
		for s in range(MAX_S + 1):
			ans = min(ans, dp[v][s])
		print(ans)

def __starting_point():
	solve()
__starting_point()


import sys
import heapq

def dijkstra(s, es):
	INF = sys.maxsize
	cs = [INF] * len(es)
	(cs[s], hq) = (0, [])
	heapq.heapify(hq)
	heapq.heappush(hq, (cs[s], s))
	while hq:
		(d, v) = heapq.heappop(hq)
		if cs[v] < d:
			continue
		for (t, b) in es[v]:
			if cs[t] > cs[v] + b:
				cs[t] = cs[v] + b
				heapq.heappush(hq, (cs[t], t))
	return cs

def nwc(n, c):
	MAX_COINS = 2500
	return (MAX_COINS + 1) * n + c

def main():
	MAX_COINS = 2500
	(N, M, S) = tuple(map(int, sys.stdin.readline().split()))
	S = S if S < MAX_COINS else MAX_COINS
	es = [[] for _ in range(N * (MAX_COINS + 1))]
	for _ in range(M):
		(u, v, a, b) = tuple(map(int, sys.stdin.readline().split()))
		(u, v) = (u - 1, v - 1)
		for c in range(a, MAX_COINS + 1):
			es[nwc(u, c)].append((nwc(v, c - a), b))
			es[nwc(v, c)].append((nwc(u, c - a), b))
	for n in range(N):
		(c, d) = tuple(map(int, sys.stdin.readline().split()))
		c = c if c < MAX_COINS else MAX_COINS
		for i in range(0, MAX_COINS - c + 1):
			es[nwc(n, i)].append((nwc(n, i + c), d))
	cs = dijkstra(nwc(0, S), es)
	for n in range(1, N):
		print(min(cs[n * (MAX_COINS + 1):(n + 1) * (MAX_COINS + 1)]))
main()


import sys
input = sys.stdin.readline
import heapq as hp
AM = 50 * 50 + 1
INF = 10 ** 15
(N, M, S) = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	graph[u - 1].append((a, b, v - 1))
	graph[v - 1].append((a, b, u - 1))
C = []
D = []
for _ in range(N):
	(c, d) = map(int, input().split())
	C.append(c)
	D.append(d)
dp = [[INF] * (AM + 1) for _ in range(N)]
dp[0][min(AM, S)] = 0
q = [(0, min(AM, S), 0)]
while q:
	(dis, cost, p) = hp.heappop(q)
	if dp[p][cost] < dis:
		continue
	if 0 <= cost + C[p] <= AM and dp[p][cost + C[p]] > dp[p][cost] + D[p]:
		dp[p][cost + C[p]] = dp[p][cost] + D[p]
		hp.heappush(q, (dp[p][cost + C[p]], cost + C[p], p))
	for (a, b, np) in graph[p]:
		if 0 <= cost - a <= AM and dp[np][cost - a] > dp[p][cost] + b:
			dp[np][cost - a] = dp[p][cost] + b
			hp.heappush(q, (dp[np][cost - a], cost - a, np))
for n in range(1, N):
	print(min(dp[n]))


def main():
	import heapq
	(n, m, s) = list(map(int, input().split()))
	if s >= 2500:
		s = 2499
	edges = [[] for _ in range(n)]
	for _ in range(m):
		(from_, to, cost, time) = list(map(int, input().split()))
		edges[from_ - 1].append((to - 1, cost, time))
		edges[to - 1].append((from_ - 1, cost, time))
	banks = []
	for i in range(n):
		(coin, time) = list(map(int, input().split()))
		banks.append((coin, time))
	INF = float('INF')
	DP = [[INF] * 2500 for _ in range(n)]
	ans = [INF] * n

	def push_todo(node, coin, time):
		if coin < 0:
			return
		if time >= DP[node][coin]:
			return
		heapq.heappush(todo, (time, node, coin))

	def charge(node, current_coin, current_time):
		(coin, time) = banks[node]
		new_coin = current_coin + coin
		if new_coin >= 2500:
			new_coin = 2499
		push_todo(node, new_coin, current_time + time)
	todo = [(0, 0, s)]
	while todo:
		(current_time, node, current_coin) = heapq.heappop(todo)
		if current_time >= DP[node][current_coin]:
			continue
		if current_time < ans[node]:
			ans[node] = current_time
		DP[node][current_coin] = current_time
		charge(node, current_coin, current_time)
		for (to, cost, time) in edges[node]:
			push_todo(to, current_coin - cost, current_time + time)
	for a in ans[1:]:
		print(a)

def __starting_point():
	main()
__starting_point()


(N, M, S) = map(int, input().split())
ways = [[] for _ in range(N)]
CD = [[0] * 2 for _ in range(N)]

class Way:

	def __init__(self, t, f, ti):
		self.to = t
		self.fare = f
		self.time = ti
for i in range(M):
	(U, V, A, B) = map(int, input().split())
	U -= 1
	V -= 1
	ways[U].append(Way(V, A, B))
	ways[V].append(Way(U, A, B))
for i in range(N):
	(C, D) = map(int, input().split())
	CD[i][0] = C
	CD[i][1] = D
dp = [[float('inf')] * (50 * N + 1) for _ in range(N)]
S = min(S, 50 * N)
dp[0][S] = 0
import heapq
q = []
heapq.heappush(q, (0, 0, S))

def Push(time, station, money):
	global q, dp
	if money < 0:
		return
	money = min(money, 50 * N)
	if dp[station][money] <= time:
		return
	dp[station][money] = time
	heapq.heappush(q, (time, station, money))
while q:
	dat = heapq.heappop(q)
	(time, station, money) = (dat[0], dat[1], dat[2])
	if dp[station][money] != time:
		continue
	Push(time + CD[station][1], station, money + CD[station][0])
	for w in ways[station]:
		Push(time + w.time, w.to, money - w.fare)
for i in range(1, N):
	ans = float('inf')
	for j in range(50 * N + 1):
		ans = min(ans, dp[i][j])
	print(ans)


import heapq
(N, M, S) = list(map(int, input().strip().split()))
graph = [[] for _ in range(N)]
for _ in range(M):
	(u, v, A, B) = list(map(int, input().strip().split()))
	u -= 1
	v -= 1
	graph[u].append((v, A, B))
	graph[v].append((u, A, B))
exchanges = []
for _ in range(N):
	(C, D) = list(map(int, input().strip().split()))
	exchanges.append((C, D))
queue = [(0, 0, S)]
max_fare = 2500
state_table = [[None] * (max_fare + 1) for i in range(N)]
reached = [False] * N
reached_count = 0
while queue:
	(time, cur, money) = heapq.heappop(queue)
	if not reached[cur]:
		reached[cur] = True
		reached_count += 1
		if reached_count >= N:
			break
	(count, d_time) = exchanges[cur]
	for (n, A, B) in graph[cur]:
		n_money = money - A
		n_time = time + B
		if n_money >= 0:
			states = state_table[n]
			if n_money > max_fare:
				n_money = max_fare
			if states[n_money] == None or states[n_money] > n_time:
				states[n_money] = n_time
				heapq.heappush(queue, (n_time, n, n_money))
	states = state_table[cur]
	money += count
	time += d_time
	if money >= 0:
		if money > max_fare:
			money = max_fare
		if states[money] == None or states[money] > time:
			states[money] = time
			heapq.heappush(queue, (time, cur, money))
for i in range(1, N):
	states = state_table[i]
	minimum = None
	for t in states:
		if t != None and (minimum == None or minimum > t):
			minimum = t
	print(minimum)


from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np
(N, M, S) = map(int, input().split())
Us = [0] * M
Vs = [0] * M
As = [0] * M
Bs = [0] * M
for i in range(M):
	(Us[i], Vs[i], As[i], Bs[i]) = map(int, input().split())
	Us[i] -= 1
	Vs[i] -= 1
V = {}
Ns = max(As) * N
Nv = N * (Ns + 1)
cnt = 0
for i in range(N):
	for ns in range(Ns + 1):
		V[i, ns] = cnt
		cnt += 1
row = []
col = []
data = []
if S > Ns:
	S = Ns
for _ in range(M):
	u = Us.pop()
	v = Vs.pop()
	a = As.pop()
	b = Bs.pop()
	for i in range(Ns + 1):
		ns_s = Ns - i
		ns_g = ns_s - a
		if ns_g >= 0:
			row.append(V[u, ns_s])
			col.append(V[v, ns_g])
			data.append(b)
			row.append(V[v, ns_s])
			col.append(V[u, ns_g])
			data.append(b)
for i in range(N):
	(c, d) = map(int, input().split())
	for j in range(Ns):
		ns_s = j
		ns_g = j + c
		if ns_g > Ns:
			ns_g = Ns
		row.append(V[i, ns_s])
		col.append(V[i, ns_g])
		data.append(d)
graph = coo_matrix((data, (row, col)), shape=(Nv, Nv))
s = V[0, S]
dist_matrix = dijkstra(csgraph=graph, directed=True, indices=s)
for i in range(1, N):
	ans = min([dist_matrix[i * (Ns + 1) + v] for v in range(Ns + 1)])
	print(int(ans))


(N, M, S) = list(map(int, input().split(' ')))
adj = [[] for _ in range(N)]
convert = []
for _ in range(M):
	(u, v, a, b) = list(map(int, input().split(' ')))
	adj[u - 1].append((v - 1, a, b))
	adj[v - 1].append((u - 1, a, b))
for _ in range(N):
	(c, d) = list(map(int, input().split(' ')))
	convert.append((c, d))
import heapq
limit = 2500
S = min(S, limit)
h = [(0, 0, S)]
ans = [[float('inf')] * (limit + 1) for _ in range(N)]
while h != []:
	(time_consumed, city, coin) = heapq.heappop(h)
	if ans[city][coin] < time_consumed:
		continue
	ans[city][coin] = time_consumed
	if coin + convert[city][0] < limit and ans[city][coin + convert[city][0]] > time_consumed + convert[city][1]:
		ans[city][coin + convert[city][0]] = time_consumed + convert[city][1]
		heapq.heappush(h, (time_consumed + convert[city][1], city, coin + convert[city][0]))
	for (v, a, b) in adj[city]:
		if coin - a < 0 or ans[v][coin - a] <= time_consumed + b:
			continue
		ans[v][coin - a] = time_consumed + b
		heapq.heappush(h, (time_consumed + b, v, coin - a))
for i in range(1, N):
	print(min(ans[i]))


def main():
	import dataclasses
	from heapq import heappush, heappop

	@dataclasses.dataclass(frozen=True)
	class Path:
		to: int
		fare: int
		travel_time: int

	@dataclasses.dataclass(frozen=True)
	class ExchangeRate:
		Ag: int
		exchange_time: int

	@dataclasses.dataclass(frozen=True)
	class Traveler:
		consumption_time: int
		remaining_Ag: int
		location: int

		def __gt__(self, other):
			return self.consumption_time > other.consumption_time

		def __eq__(self, other):
			return self.consumption_time == other.consumption_time
	INF = 1 << 60
	MX_AG = 2500
	(N, M, S) = list(map(int, input().split()))
	S = min(S, MX_AG)
	g = tuple((set() for _ in range(N)))
	for _ in range(M):
		(u, v, a, b) = list(map(int, input().split()))
		u -= 1
		v -= 1
		g[u].add(Path(v, a, b))
		g[v].add(Path(u, a, b))
	exchange = []
	for _ in range(N):
		(c, d) = list(map(int, input().split()))
		exchange.append(ExchangeRate(c, d))
	h = [Traveler(0, S, 0)]
	time = [[INF] * (MX_AG + 1) for _ in range(N)]
	time[0][S] = 0
	while h:
		t = heappop(h)
		for p in g[t.location]:
			n_Ag = t.remaining_Ag - p.fare
			if n_Ag < 0:
				continue
			cf = time[p.to][n_Ag]
			n_time = t.consumption_time + p.travel_time
			if cf <= n_time:
				continue
			time[p.to][n_Ag] = n_time
			heappush(h, Traveler(consumption_time=n_time, remaining_Ag=n_Ag, location=p.to))
		e_time = t.consumption_time + exchange[t.location].exchange_time
		e_Ag = t.remaining_Ag + exchange[t.location].Ag
		if e_Ag > MX_AG:
			continue
		cf = time[t.location][e_Ag]
		if cf <= e_time:
			continue
		time[t.location][e_Ag] = e_time
		heappush(h, Traveler(consumption_time=e_time, remaining_Ag=e_Ag, location=t.location))
	for to in range(1, N):
		print(min(time[to]))

def __starting_point():
	main()
__starting_point()


from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
	(N, M, S) = map(int, readline().split())
	E = [[] for _ in range(N + 1)]
	for _ in range(M):
		(u, v, a, b) = map(int, readline().split())
		E[u].append((v, a, b))
		E[v].append((u, a, b))
	cd = map(int, read().split())
	CD = []
	for (c, d) in zip(*[iter(cd)] * 2):
		CD.append((c, d))
	if S > 2500:
		S = 2500 - 1
	INF = 10 ** 15
	d = [[INF] * 2500 for _ in range(N + 1)]
	d[1][S] = 0
	Q = []
	heappush(Q, (0, S, 1))
	while Q:
		(time, s, u) = heappop(Q)
		if time > d[u][s]:
			continue
		(c_u, d_u) = CD[u - 1]
		if s + c_u < 2500 and time + d_u < d[u][s + c_u]:
			d[u][s + c_u] = time + d_u
			heappush(Q, (time + d_u, s + c_u, u))
		for (v, a, b) in E[u]:
			if s >= a and time + b < d[v][s - a]:
				d[v][s - a] = time + b
				heappush(Q, (time + b, s - a, v))
	for i in range(2, N + 1):
		print(min(d[i]))
main()


(n, m, s) = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	edges[u].append((v, a, b))
	edges[v].append((u, a, b))
banks = tuple((tuple(map(int, input().split())) for _ in range(n)))
max_s = 50 * (n - 1)
s = min(s, max_s)
import heapq
h = []
dp = [[float('inf')] * (max_s + 1) for _ in range(n)]
ans = [float('inf')] * n
heapq.heappush(h, (0, 0, s))
while h:
	(time, node, coin) = heapq.heappop(h)
	if time >= dp[node][coin]:
		continue
	dp[node][coin] = time
	if time < ans[node]:
		ans[node] = time
	(c, d) = banks[node]
	if coin < max_s:
		heapq.heappush(h, (time + d, node, min(coin + c, max_s)))
	for (n, a, b) in edges[node]:
		new_time = time + b
		new_coin = coin - a
		if new_coin < 0 or new_time >= dp[n][new_coin]:
			continue
		heapq.heappush(h, (new_time, n, new_coin))
for a in ans[1:]:
	print(a)


import numpy as np
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.csgraph import shortest_path
M = 49 * 50 + 1
(n, m, s) = map(int, input().split())
s = min(s, M - 1)
G = lil_matrix((n * M, n * M))
for _ in range(m):
	(a, b, silver, time) = map(int, input().split())
	a -= 1
	b -= 1
	for i in range(silver, M):
		G[a * M + i, b * M + i - silver] = time
		G[b * M + i, a * M + i - silver] = time
for i in range(n):
	(silver, time) = map(int, input().split())
	for j in range(M - 1):
		G[i * M + j, i * M + min(j + silver, M - 1)] = time
G = G.tocsr()
G = shortest_path(G, method='D', indices=s)
for i in range(1, n):
	ans = np.min(G[i * M:i * M + M])
	print(int(ans))


from heapq import heappop, heappush
import sys

def main():
	input = sys.stdin.readline
	(N, M, S) = map(int, input().split())
	G1 = [[] for _ in range(N)]
	for _ in range(M):
		(u, v, a, b) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		G1[u].append((b, a, v))
		G1[v].append((b, a, u))
	G2 = [tuple(map(int, input().split())) for _ in range(N)]
	q = [(0, (0, S))]
	T = [-1] * N
	lenT = 0
	visited = set()
	MX = 50 * (N - 1)
	while q:
		(t, V) = heappop(q)
		(v, s) = V
		if T[v] < 0:
			T[v] = t
			lenT += 1
			if lenT >= N:
				break
		if V in visited:
			continue
		visited.add(V)
		for (dt, ds, to) in G1[v]:
			if s < ds:
				continue
			nV = (to, s - ds)
			if nV in visited:
				continue
			heappush(q, (t + dt, nV))
		(c, d) = G2[v]
		if s + c <= MX:
			heappush(q, (t + d, (v, s + c)))
	for i in range(1, N):
		print(T[i])
main()


import heapq
(n, m, s) = map(int, input().split())
s = min(s, 2499)
UV = [[] for _ in range(n)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	UV[u].append((v, a, b))
	UV[v].append((u, a, b))
CD = [tuple(map(int, input().split())) for _ in range(n)]
MAXS = 2500
NV = MAXS * n
edges = [[] for _ in range(NV)]

def to_v(i, j):
	return MAXS * i + j
for (i, (c, d)) in enumerate(CD):
	for j in range(MAXS - c):
		edges[to_v(i, j)].append((d, to_v(i, j) + c))
for i in range(n):
	for (i2, a, b) in UV[i]:
		for j in range(MAXS - a):
			edges[to_v(i, a + j)].append((b, to_v(i2, j)))

def dijkstra(init_v):
	next_v = [(0, init_v)]
	INF = 10 ** 18
	dist = [INF] * NV
	dist[init_v] = 0
	while next_v:
		(d, v) = heapq.heappop(next_v)
		if dist[v] < d:
			continue
		for (d, v2) in edges[v]:
			if dist[v2] <= dist[v] + d:
				continue
			dist[v2] = dist[v] + d
			heapq.heappush(next_v, (dist[v2], v2))
	return dist
INF = 10 ** 18
dist = dijkstra(s)
for i in range(1, n):
	ans = INF
	for j in range(MAXS):
		ans = min(ans, dist[to_v(i, j)])
	print(ans)


import sys, math, itertools, collections, bisect, heapq
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
mans = inf
ans = 0
count = 0
pro = 1
(n, m, s0) = map(int, input().split())
s0 = min(2500, s0)
G = [[] for i in range(n)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	G[u].append((v, -a, b))
	G[v].append((u, -a, b))
for i in range(n):
	(c, d) = map(int, input().split())
	G[i].append((i, c, d))

def dijktra(g, s):
	n = len(g)
	dist = [[inf] * 2501 for i in range(n)]
	dist[s][s0] = 0
	hq = []
	heapq.heappush(hq, (0, s0, s))
	while hq:
		(time, money, u) = heapq.heappop(hq)
		if dist[u][money] < time:
			continue
		for (v, money1, time1) in g[u]:
			M = min(2500, money + money1)
			if not M >= 0:
				continue
			if dist[v][M] > time + time1:
				dist[v][M] = time + time1
				heapq.heappush(hq, (time + time1, M, v))
	return dist
dist = dijktra(G, 0)
for i in range(1, n):
	print(min(dist[i]))


from heapq import heappop, heappush
(n, m, s) = map(int, input().split())
e = [[] for _ in range(n)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	e[u].append((v, a, b))
	e[v].append((u, a, b))
c = []
d = []
for i in range(n):
	(x, y) = map(int, input().split())
	c.append(x)
	d.append(y)
INF = float('inf')

def dijkstra(s, n, g):
	que = []
	d = [INF for _ in range(n)]
	d[s] = 0
	heappush(que, (0, s))
	while len(que) > 0:
		p = heappop(que)
		v = p[1]
		if d[v] < p[0]:
			continue
		for (u, w) in g[v]:
			if d[u] > d[v] + w:
				d[u] = d[v] + w
				heappush(que, (d[u], u))
	return d

def newv(v, s):
	return v * 2500 + s
s = min(s, 2499)
e2 = [[] for _ in range(n * 2500)]
for u in range(n):
	for j in range(2500):
		if j + c[u] < 2500:
			e2[newv(u, j)].append((newv(u, j + c[u]), d[u]))
		for (v, a, b) in e[u]:
			if j >= a:
				e2[newv(u, j)].append((newv(v, j - a), b))
l = dijkstra(newv(0, s), n * 2500, e2)
for i in range(1, n):
	ans = INF
	for j in range(2500):
		ans = min(l[newv(i, j)], ans)
	print(ans)


import sys
readline = sys.stdin.readline
read = sys.stdin.read
(n, m, s) = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
	(u, v, a, b) = [int(i) for i in readline().split()]
	u -= 1
	v -= 1
	g[u].append((v, a, b))
	g[v].append((u, a, b))
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
from heapq import *
INF = 1 << 61
M = 2500
if s >= M:
	s = M - 1
dist = [[INF] * M for _ in range(n)]
dist[0][s] = 0
q = [(0, s, 0)]
while q:
	(dv, num, v) = heappop(q)
	if dist[v][num] < dv:
		continue
	if num + c[v] < M and dv + d[v] < dist[v][num + c[v]]:
		dist[v][num + c[v]] = dv + d[v]
		heappush(q, (dv + d[v], num + c[v], v))
	for (to, a, b) in g[v]:
		if num >= a and dv + b < dist[to][num - a]:
			dist[to][num - a] = dv + b
			heappush(q, (dv + b, num - a, to))
for i in range(1, n):
	print(min(dist[i]))


from heapq import heappop, heappush

def main():
	(N, M, S) = map(int, input().split())
	adj = [{} for _ in range(N)]
	amax = 0
	for _ in range(M):
		(u, v, a, b) = map(int, input().split())
		adj[u - 1][v - 1] = (a, b)
		adj[v - 1][u - 1] = (a, b)
		amax = max(amax, a)
	C = [0] * N
	D = [0] * N
	for i in range(N):
		(C[i], D[i]) = map(int, input().split())
	MAX = amax * N
	dp = [[float('inf')] * (MAX + 1) for _ in range(N)]
	q = [[0, min(S, MAX), 0, -1]]
	ans = [None] * N
	remain = N
	while len(q) and remain:
		(time, coin, cur, prev) = heappop(q)
		if dp[cur][coin] <= time:
			continue
		if ans[cur] is None:
			ans[cur] = time
			remain -= 1
		dp[cur][coin] = time
		if coin < MAX:
			heappush(q, [time + D[cur], min(coin + C[cur], MAX), cur, cur])
		for nxt in adj[cur]:
			(dcost, dtime) = adj[cur][nxt]
			if nxt != prev and dcost <= coin:
				heappush(q, [time + dtime, coin - dcost, nxt, cur])
	for i in range(1, N):
		print(ans[i])
main()


import heapq
(n, m, s) = map(int, input().split())
limit = 2500
s = min(s, limit)
path = [[] for _ in range(n + 1)]
coin = [(0, 0)]
time = [[float('inf') for _ in range(limit + 1)] for _ in range(n + 1)]
queue = []
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	path[u].append((v, a, b))
	path[v].append((u, a, b))
for i in range(n):
	(c, d) = map(int, input().split())
	coin.append((c, d))
time[1][s] = 0
heapq.heappush(queue, (0, 1, s))
while len(queue) != 0:
	(t, v, c) = heapq.heappop(queue)
	for (nv, na, nb) in path[v]:
		if na > c:
			continue
		elif time[nv][c - na] <= t + nb:
			continue
		else:
			time[nv][c - na] = t + nb
			heapq.heappush(queue, (t + nb, nv, c - na))
	nc = min(c + coin[v][0], limit)
	nt = t + coin[v][1]
	if time[v][nc] <= nt:
		continue
	else:
		time[v][nc] = nt
		heapq.heappush(queue, (nt, v, nc))
for i in range(2, n + 1):
	print(min(time[i]))


import sys
input = lambda : sys.stdin.readline().rstrip()
(n, m, s) = map(int, input().split())
s = min(s, 2500)
from collections import defaultdict
import heapq

def dijkstra(s, x):
	d = defaultdict(lambda : float('inf'))
	d[s, x] = 0
	used = defaultdict(lambda : False)
	used[s, x] = True
	que = []
	for e in edge[s, x]:
		heapq.heappush(que, e)
	while que:
		minedge = heapq.heappop(que)
		if used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = True
		for e in edge[v]:
			if not used[e[1]]:
				heapq.heappush(que, (e[0] + d[v], e[1]))
	return d
max_money = 2500
edge = defaultdict(list)
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for i in range(a, max_money + 1):
		edge[u, i].append((b, (v, i - a)))
		edge[v, i].append((b, (u, i - a)))
for j in range(n):
	(c, d) = map(int, input().split())
	for i in range(max_money):
		if i + c <= max_money:
			edge[j, i].append((d, (j, i + c)))
ans = [10 ** 18] * n
d = dijkstra(0, s)
for i in d:
	(x, y) = i
	cost = d[i]
	ans[x] = min(ans[x], cost)
for i in ans[1:]:
	print(i)


from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
(N, M, S) = map(int, input().split())
INF = 10 ** 18
Time = [[INF] * 2501 for _ in range(N)]
graph = [[] for _ in range(N)]
S = min(S, 2500)
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	graph[u - 1].append((v - 1, a, b))
	graph[v - 1].append((u - 1, a, b))
cd = [tuple(map(int, input().split())) for _ in range(N)]
hq = [(0, 0, S)]
while hq:
	(ct, cur_city, si) = heappop(hq)
	for (nxt_city, cost, t) in graph[cur_city]:
		if si >= cost:
			new_t = ct + t
			if new_t < Time[nxt_city][si - cost]:
				Time[nxt_city][si - cost] = new_t
				heappush(hq, (new_t, nxt_city, si - cost))
	(c, d) = cd[cur_city]
	v_new = min(si + c, 2500)
	t_new = ct + d
	if t_new < Time[cur_city][v_new]:
		Time[cur_city][v_new] = t_new
		heappush(hq, (t_new, cur_city, v_new))
for i in range(1, N):
	print(min(Time[i]))


from heapq import *
(N, M, S) = tuple(map(int, input().split()))
graph = [[] for _ in range(N)]
Max = 0
for i in range(M):
	(U, V, A, B) = tuple(map(int, input().split()))
	Max = max(Max, A)
	U -= 1
	V -= 1
	graph[U] += [(V, A, B)]
	graph[V] += [(U, A, B)]
Max *= N - 1
for i in range(N):
	(C, D) = tuple(map(int, input().split()))
	graph[i] += [(i, -C, D)]
costs = [[2 ** 64 for _ in range(Max + 1)] for _ in range(N)]
que = [(0, 0, S)]
while que:
	(cost_sum, node, coins) = heappop(que)
	for (to, pay, cost) in graph[node]:
		if coins >= pay and cost_sum + cost < costs[to][min(Max, coins - pay)]:
			costs[to][min(Max, coins - pay)] = cost_sum + cost
			heappush(que, (cost_sum + cost, to, min(Max, coins - pay)))
for i in range(1, N):
	print(min(costs[i]))


import sys
(N, M, S) = map(int, input().split())
S = min(S, 2500)
INF = 10 ** 18
dp = [[INF] * 2501 for _ in range(N)]
way = [[] for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	way[u - 1].append((v - 1, a, b))
	way[v - 1].append((u - 1, a, b))
CD = [tuple(map(int, input().split())) for _ in range(N)]
from heapq import heappush, heappop
q = [(0, 0, S)]
while q:
	(t, u, s) = heappop(q)
	for (nxt, a, b) in way[u]:
		if s >= a:
			if dp[nxt][s - a] > t + b:
				dp[nxt][s - a] = t + b
				heappush(q, (t + b, nxt, s - a))
	(c, d) = CD[u]
	nc = min(2500, c + s)
	nt = t + d
	if nt < dp[u][nc]:
		dp[u][nc] = nt
		heappush(q, (nt, u, nc))
for i in range(1, N):
	print(min(dp[i]))


(n, m, s) = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]
import math
M = 50 * n + 1
s = min(s, M - 1)
dp = [[float('inf')] * M for _ in range(n)]
dp[0][s] = 0
(c, d) = (cd[0][0], cd[0][1])
for jj in range(M):
	dp[0][jj] = min(dp[0][jj], dp[0][s] + max(math.ceil((jj - s) / c), 0) * d)
while True:
	flag = False
	for i in range(m):
		(u1, v1, a, b) = (uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3])
		for (u, v) in [(u1, v1), (v1, u1)]:
			for j in range(M - a):
				tmp = dp[u][j + a] + b
				if tmp < dp[v][j]:
					dp[v][j] = tmp
					flag = True
			(c, d) = (cd[v][0], cd[v][1])
			for jj in range(c, M):
				tmp = dp[v][jj - c] + d
				if tmp < dp[v][jj]:
					dp[v][jj] = tmp
					flag = True
	if flag == False:
		break
for t in range(1, n):
	print(min(dp[t]))


import heapq

def dijkstra_heap(N, S, Smax, edge):
	d = [float('inf')] * (10 ** 4 * N)
	used = [False] * (10 ** 4 * N)
	d[S] = 0
	used[S] = True
	edgelist = []
	for (w, a) in edge[0]:
		(v, sil) = (a // 10 ** 4, a % 10 ** 4)
		if v == 0 and S + sil <= Smax:
			heapq.heappush(edgelist, [w, a + S])
		elif v > 0 and S - sil >= 0:
			heapq.heappush(edgelist, [w, v * 10 ** 4 + (S - sil)])
	while len(edgelist):
		(min_w, min_a) = heapq.heappop(edgelist)
		(min_v, min_sil) = (min_a // 10 ** 4, min_a % 10 ** 4)
		if used[min_a]:
			continue
		d[min_a] = min_w
		used[min_a] = True
		for (w, a) in edge[min_v]:
			(v, sil) = (a // 10 ** 4, a % 10 ** 4)
			if v == min_v and min_sil + sil <= Smax and (not used[a + min_sil]):
				heapq.heappush(edgelist, [min_w + w, a + min_sil])
			elif v != min_v and min_sil - sil >= 0 and (not used[v * 10 ** 4 + (min_sil - sil)]):
				heapq.heappush(edgelist, [min_w + w, v * 10 ** 4 + (min_sil - sil)])
	return d

def solve():
	(N, M, S) = map(int, input().split())
	edge = [[] for _ in range(N)]
	amax = 0
	for i in range(M):
		(u, v, a, b) = map(int, input().split())
		amax = max(amax, a)
		edge[u - 1].append([b, (v - 1) * 10 ** 4 + a])
		edge[v - 1].append([b, (u - 1) * 10 ** 4 + a])
	Smax = (N - 1) * amax
	S = min(S, Smax)
	for i in range(N):
		(c, d) = map(int, input().split())
		edge[i].append([d, i * 10 ** 4 + c])
	D = dijkstra_heap(N, S, Smax, edge)
	ans = [0] * N
	for i in range(1, N):
		ans[i] = min(D[i * 10 ** 4:(i + 1) * 10 ** 4])
	return ans[1:]
print(*solve(), sep='\n')


from heapq import *
(N, M, S) = map(int, input().split())
graph = [[] for _ in range(N)]
amax = 0
for i in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	graph[u].append([v, a, b])
	graph[v].append([u, a, b])
	amax = max(amax, a)
lcoins = amax * (N - 1)
cost = list()
time = list()
for _ in range(N):
	(c, d) = map(int, input().split())
	cost.append(c)
	time.append(d)
INF = float('INF')
M = 2500
if S >= M:
	S = M - 1
dist = [[INF] * M for _ in range(N)]
dist[0][S] = 0
q = [(0, S, 0)]
while q:
	(dv, num, v) = heappop(q)
	if dist[v][num] < dv:
		continue
	if num + cost[v] < M and dv + time[v] < dist[v][num + cost[v]]:
		dist[v][num + cost[v]] = dv + time[v]
		heappush(q, (dv + time[v], num + cost[v], v))
	for (next, a, b) in graph[v]:
		if num >= a and dv + b < dist[next][num - a]:
			dist[next][num - a] = dv + b
			heappush(q, (dv + b, num - a, next))
for i in range(1, N):
	print(min(dist[i]))


import heapq
import sys
input = sys.stdin.readline
INF = 10 ** 18

class Edge:

	def __init__(self, end, cost, time):
		self.end = end
		self.cost = cost
		self.time = time
dp = []
h = []

def push(t, v, x):
	if x < 0:
		return
	if dp[v][x] <= t:
		return
	dp[v][x] = t
	heapq.heappush(h, (t, v, x))

def dijkstra(n, G, cd, start, s, max_s):
	nonlocal dp
	dp = [[INF for j in range(max_s + 1)] for i in range(n)]
	push(0, start, s)
	while h:
		(t, v, x) = heapq.heappop(h)
		if dp[v][x] < t:
			continue
		if x < max_s:
			push(t + cd[v][1], v, min(x + cd[v][0], max_s))
		for e in G[v]:
			push(t + e.time, e.end, x - e.cost)
(n, m, s) = list(map(int, input().split()))
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]
es = [[] for i in range(n)]
max_s = 50 * (n - 1)
for (u, v, a, b) in uvab:
	es[u - 1].append(Edge(v - 1, a, b))
	es[v - 1].append(Edge(u - 1, a, b))
dijkstra(n, es, cd, 0, min(max_s, s), max_s)
for i in range(1, n):
	print(min(dp[i]))


from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline
DEBUG = False
INF = float('inf')
MAX_N = 50
MAX_A = 50
(N, M, S) = list(map(int, input().split()))
U = []
V = []
A = []
B = []
C = []
D = []
connect = [[] for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = list(map(int, input().split()))
	U.append(u)
	V.append(v)
	A.append(a)
	B.append(b)
	connect[u - 1].append([v - 1, a, b])
	connect[v - 1].append([u - 1, a, b])
for _ in range(N):
	(c, d) = list(map(int, input().split()))
	C.append(c)
	D.append(d)
if DEBUG:
	print('U: {}'.format(U))
	print('V: {}'.format(V))
	print('A: {}'.format(A))
	print('B: {}'.format(B))
	print('C: {}'.format(C))
	print('D: {}'.format(D))
	print('connect: {}'.format(connect))
MAX_N = N
MAX_A = max(A)
MAX_MONEY = MAX_N * MAX_A
S = min(S, MAX_MONEY - 1)
node = [INF for _ in range(MAX_MONEY * N)]
hq = []
heappush(hq, (0, S))
while hq:
	(time, current_node) = heappop(hq)
	if DEBUG:
		print('time: {}, current_node: {}, len(hq): {}'.format(time, current_node, len(hq)))
	if time < node[current_node]:
		node[current_node] = time
	else:
		continue
	index_city = current_node // MAX_MONEY
	money = current_node % MAX_MONEY
	if DEBUG:
		print('money: {}'.format(money))
	for (index_next_city, a, b) in connect[index_city]:
		if money >= a and time + b < node[index_next_city * MAX_MONEY + money - a]:
			heappush(hq, (time + b, index_next_city * MAX_MONEY + money - a))
	if money < MAX_MONEY - 1:
		heappush(hq, (time + D[index_city], min(money + C[index_city], MAX_MONEY - 1) + MAX_MONEY * index_city))
for i in range(1, N):
	if DEBUG:
		print('node{}: {}'.format(i, node[MAX_MONEY * i:MAX_MONEY * (i + 1)]))
	print(min(node[MAX_MONEY * i:MAX_MONEY * (i + 1)]))


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	(n, m, s) = map(int, input().split())
	E = [None] * m
	S = 0
	for i in range(m):
		(u, v, a, b) = map(int, input().split())
		S += a
		E[i] = (u - 1, v - 1, -a, b)
	exchange = [tuple(map(int, input().split())) for _ in range(n)]
	dp = [[INF] * (S + 1) for _ in range(n)]
	dp[0][min(s, S)] = 0
	for _ in range(2 * n - 3):
		for v in range(n):
			for s in range(S + 1):
				(ds, dt) = exchange[v]
				dp[v][min(s + ds, S)] = min(dp[v][min(s + ds, S)], dp[v][s] + dt)
		for (u, v, ds, dt) in E:
			for s in range(S + 1):
				ns = s + ds
				if ns < 0:
					continue
				dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)
				dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)
	for v in range(1, n):
		print(min((dp[v][j] for j in range(S + 1))))
resolve()


from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
from heapq import heappush, heappop
INF = 10 ** 18
(N, M, S) = map(int, input().split())
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]
sumA = 0
for (u, v, a, b) in UVAB:
	sumA += a

def dijkstra(start, graph) -> list:
	dist = [[INF for _ in range(N + 1)] for _ in range(sumA + 1)]
	dist[start][1] = 0
	heap = []
	heappush(heap, (0, (start, 1)))
	while heap:
		(v, (i, j)) = heappop(heap)
		for (w, (ni, nj)) in graph[i][j]:
			if dist[ni][nj] > v + w:
				dist[ni][nj] = v + w
				heappush(heap, (dist[ni][nj], (ni, nj)))
	return dist
graph = [[[] for _ in range(N + 1)] for _ in range(sumA + 1)]
for (u, v, a, b) in UVAB:
	for i in range(a, sumA + 1):
		graph[i][u].append((b, (i - a, v)))
		graph[i][v].append((b, (i - a, u)))
for j in range(1, N + 1):
	(c, d) = CD[j - 1]
	for i in range(sumA):
		graph[i][j].append((d, (min(i + c, sumA), j)))
dist = dijkstra(min(S, sumA), graph)
for j in range(2, N + 1):
	answer = INF
	for i in range(sumA + 1):
		answer = min(dist[i][j], answer)
	print(answer)


import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
input = sys.stdin.readline
(N, M, S) = map(int, input().split())
S = min(S, 2500)
row = []
col = []
data = []
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for i in range(a, 2501):
		row.append(N * i + u)
		col.append(N * (i - a) + v)
		data.append(b)
		row.append(N * i + v)
		col.append(N * (i - a) + u)
		data.append(b)
for u in range(N):
	(c, d) = map(int, input().split())
	for i in range(1, c):
		row.append(N * (2500 - i) + u)
		col.append(N * 2500 + u)
		data.append(d)
	for i in range(c, 2501):
		row.append(N * (i - c) + u)
		col.append(N * i + u)
		data.append(d)
graph = csr_matrix((data, (row, col)), shape=(2501 * N, 2501 * N))
times = dijkstra(graph, directed=True, indices=N * S)
for end in range(1, N):
	print(int(min((times[N * i + end] for i in range(2501)))))


(n, m, s) = list(map(int, input().split()))
s = min(s, 2500)
edge = [[[] for i in range(50 * 50 + 1)] for i in range(n)]
for i in range(m):
	(u, v, a, b) = list(map(int, input().split()))
	for j in range(a, 2501):
		edge[u - 1][j].append((v - 1, j - a, b))
		edge[v - 1][j].append((u - 1, j - a, b))
for i in range(n):
	(c, d) = list(map(int, input().split()))
	for j in range(2500):
		if j + c >= 2500:
			edge[i][j].append((i, 2500, d))
		elif j + c < 2500:
			edge[i][j].append((i, j + c, d))
from heapq import heappush, heappop, heapify
d = [[float('inf') for i in range(50 * 50 + 1)] for i in range(n)]
d[0][s] = 0
pq = []
heappush(pq, (0, 0, s))
while len(pq):
	(_, u, g) = heappop(pq)
	for tuple in edge[u][g]:
		if d[tuple[0]][tuple[1]] > d[u][g] + tuple[2]:
			d[tuple[0]][tuple[1]] = d[u][g] + tuple[2]
			heappush(pq, [d[u][g] + tuple[2], tuple[0], tuple[1]])
for i in range(1, n):
	print(min(d[i]))


import heapq
import os
from collections import defaultdict
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(N, M, S) = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD
graph = [[] for _ in range(N + 1)]
for (u, v, a, b) in UVAB:
	graph[u].append((a, b, v))
	graph[v].append((a, b, u))
for vs in graph:
	vs.sort()
mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
dp = defaultdict(lambda : INF)
dp[1, S] = 0
while heap and mada:
	(d, v, s) = heapq.heappop(heap)
	if d > dp[v, s]:
		continue
	if v in mada:
		mada.remove(v)
	ans[v] = min(ans[v], d)
	for (a, b, u) in graph[v]:
		if s - a < 0:
			break
		if d + b < dp[u, s - a]:
			dp[u, s - a] = d + b
			heapq.heappush(heap, (d + b, u, s - a))
	(c, dd) = CD[v]
	sc = min(s + c, 50 * N + 10)
	if d + dd < dp[v, sc]:
		dp[v, sc] = d + dd
		heapq.heappush(heap, (d + dd, v, sc))
print(*ans[2:], sep='\n')


import heapq

def dijkstra(s, n, g):
	INF = 10 ** 18
	d = [INF] * n
	d[s] = 0
	que = []
	heapq.heappush(que, (0, s))
	while que:
		(dist, v) = heapq.heappop(que)
		if d[v] < dist:
			continue
		for (next_v, cost) in g[v]:
			if d[next_v] > d[v] + cost:
				d[next_v] = d[v] + cost
				heapq.heappush(que, (d[next_v], next_v))
	return d

def main():
	(n, m, s) = map(int, input().split())
	g = [[] for _ in range(n * 2501 + 1)]
	for _ in range(m):
		(u, v, a, b) = map(int, input().split())
		u -= 1
		v -= 1
		for j in range(2501):
			if j < a:
				continue
			g[u * 2501 + j].append((v * 2501 + j - a, b))
			g[v * 2501 + j].append((u * 2501 + j - a, b))
	cdl = [(-1, -1)]
	for i in range(n):
		(c, d) = map(int, input().split())
		for j in range(2501):
			maxc = min(2500, j + c)
			g[i * 2501 + j].append((i * 2501 + maxc, d))
	s = min(2500, s)
	dist = dijkstra(s, n * 2501 + 1, g)
	for i in range(1, n):
		ans = min(dist[i * 2501:i * 2501 + 2500])
		print(ans)
main()


import sys
input = sys.stdin.readline

def main():
	(n, m, s) = map(int, input().split())
	uvab = [list(map(int, input().split())) for _ in range(m)]
	cd = [list(map(int, input().split())) for _ in range(n)]
	g = [[] for _ in range(n)]
	for (u, v, a, b) in uvab:
		g[u - 1].append((v - 1, a, b))
		g[v - 1].append((u - 1, a, b))
	import heapq
	inf = pow(10, 21)
	max_s = 50 * 50
	dp = [[inf] * (max_s + 1) for _ in range(n)]
	kakutei = [[0] * (max_s + 1) for _ in range(n)]
	dp[0][min(s, max_s)] = 0
	todo = [[0, 0, min(s, max_s)]]
	heapq.heapify(todo)
	flgs = [0] * n
	flg = 0
	ans = [inf] * n
	while flg < n:
		(_, v, i) = heapq.heappop(todo)
		if kakutei[v][i] == 1:
			continue
		kakutei[v][i] = 1
		if flgs[v] == 0:
			flg += 1
			flgs[v] = 1
		(c, d) = cd[v]
		ans[v] = min(ans[v], _)
		j = min(max_s, i + c)
		if kakutei[v][j] == 0:
			dp[v][j] = min(dp[v][j], dp[v][i] + d)
			heapq.heappush(todo, [dp[v][j], v, j])
		l = g[v]
		for (u, a, b) in l:
			if i - a >= 0 and kakutei[u][i - a] == 0:
				dp[u][i - a] = min(dp[u][i - a], dp[v][i] + b)
				heapq.heappush(todo, [dp[u][i - a], u, i - a])
	print(*ans[1:], sep='\n')

def __starting_point():
	main()
__starting_point()


import heapq
INF = 10 ** 20
(N, M, S) = map(int, input().split())
adj = [[] for _ in range(N)]
for m in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append((v, a, b))
	adj[v].append((u, a, b))
C = []
D = []
for n in range(N):
	(c, d) = map(int, input().split())
	C.append(c)
	D.append(d)
M = 2500
S = min(S, M - 1)
dist = [[INF] * M for _ in range(N)]
dist[0][S] = 0
pq = [(0, S, 0)]
while pq:
	(d, sil, node) = heapq.heappop(pq)
	if dist[node][sil] < d:
		continue
	if sil + C[node] < M and d + D[node] < dist[node][sil + C[node]]:
		dist[node][sil + C[node]] = d + D[node]
		heapq.heappush(pq, (d + D[node], sil + C[node], node))
	for (next, a, b) in adj[node]:
		if sil >= a and d + b < dist[next][sil - a]:
			dist[next][sil - a] = d + b
			heapq.heappush(pq, (d + b, sil - a, next))
for i in range(1, N):
	print(min(dist[i]))


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
(n, m, s) = LI()
s = min(s, 2500)
uvab = [LI() for _ in range(m)]
cd = [LI() for _ in range(n)]
dp = [[inf] * (2500 + 1) for _ in range(n + 1)]
dp[0][s] = 0
edges = [[] for _ in range(n)]
exchange = [[c, d] for (c, d) in cd]
for (u, v, a, b) in uvab:
	edges[u - 1].append((v - 1, a, b))
	edges[v - 1].append((u - 1, a, b))
for (i, (c, d)) in enumerate(cd):
	edges[i].append((i, -c, d))
h = [(0, 0, s)]
while h:
	(dist, u, coin) = heappop(h)
	if dp[u][coin] < dist:
		continue
	for (v, a, b) in edges[u]:
		if 2500 >= coin - a >= 0:
			if dp[u][coin] + b < dp[v][coin - a]:
				dp[v][coin - a] = dp[u][coin] + b
				heappush(h, (dp[v][coin - a], v, coin - a))
for i in range(1, n):
	print(min(dp[i]))


import heapq
import sys

def main():
	(n, m, s) = map(int, input().split())
	uvab = [list(map(int, input().split())) for _ in range(m)]
	cd = [list(map(int, input().split())) for _ in range(n)]
	edges = [[[] for _ in range(n)] for _ in range(2501)]
	for (u, v, a, b) in uvab:
		for i in range(a, 2501):
			edges[i][u - 1].append(((v - 1, i - a), b))
			edges[i][v - 1].append(((u - 1, i - a), b))
	for i in range(n):
		(c, d) = cd[i]
		for j in range(2501):
			edges[j][i].append(((i, min(j + c, 2500)), d))

	def dijkstra(edges, c):
		hq = []
		d = [[10 ** 20] * n for _ in range(c)]
		d[min(2500, s)][0] = 0
		heapq.heappush(hq, (0, (0, min(2500, s))))
		while hq:
			(d1, p) = heapq.heappop(hq)
			for (p2, d2) in edges[p[1]][p[0]]:
				if d[p2[1]][p2[0]] == -1 or d[p2[1]][p2[0]] > d1 + d2:
					d[p2[1]][p2[0]] = d1 + d2
					heapq.heappush(hq, (d1 + d2, p2))
		return d
	dis = dijkstra(edges, 2501)
	ans = [10 ** 20] * n
	for i in range(2501):
		for j in range(n):
			ans[j] = min(ans[j], dis[i][j])
	for i in ans[1:]:
		print(i)
main()


def main():
	import heapq
	inf = 10 ** 16
	(n, m, s) = map(int, input().split())
	uvab = [list(map(int, input().split())) for _ in [0] * m]
	cd = [list(map(int, input().split())) for _ in [0] * n]
	g = [[] for _ in [0] * n]
	[g[a - 1].append([b - 1, c, d]) for (a, b, c, d) in uvab]
	[g[b - 1].append([a - 1, c, d]) for (a, b, c, d) in uvab]
	vertex = [[inf] * 2501 for _ in [0] * n]
	h = [(0, 0, min(s, 2500))]
	heapq.heapify(h)
	while h:
		(t, p, money) = heapq.heappop(h)
		if vertex[p][money] != inf:
			continue
		vertex[p][money] = t
		newmoney = min(money + cd[p][0], 2500)
		if vertex[p][newmoney] == inf:
			heapq.heappush(h, (t + cd[p][1], p, newmoney))
		for (a, b, c) in g[p]:
			if money < b:
				continue
			if vertex[a][money - b] != inf:
				continue
			heapq.heappush(h, (t + c, a, money - b))
	for i in vertex[1:]:
		print(min(i))
main()


import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
(N, M, S) = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	edge[u].append((v, a, b))
	edge[v].append((u, a, b))
CD = tuple((tuple(map(int, input().split())) for _ in range(N)))
inf = 10 ** 18
U = N * 50
S = min(S, U)
dist = [[inf] * (U + 1) for _ in range(N)]
dist[0][S] = 0
que = [(0, -S, 0)]
while que:
	(time, silver, now) = heapq.heappop(que)
	silver = -silver
	if dist[now][silver] < time:
		continue
	(c, d) = CD[now]
	n = 1
	while silver + c * n <= U:
		if dist[now][silver + c * n] > time + n * d:
			dist[now][silver + c * n] = time + n * d
			heapq.heappush(que, (time + n * d, -(silver + c * n), now))
			n += 1
		else:
			break
	for (nxt, s, t) in edge[now]:
		if silver < s:
			continue
		if dist[nxt][silver - s] > time + t:
			dist[nxt][silver - s] = time + t
			heapq.heappush(que, (time + t, -(silver - s), nxt))
for i in range(1, N):
	print(min(dist[i]))


(n, m, s) = map(int, input().split())
road = [[] for _ in range(n)]
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	road[u].append([v, a, b])
	road[v].append([u, a, b])
coin = []
for _ in range(n):
	(c, d) = map(int, input().split())
	coin.append([c, d])
if s >= 2500:
	s = 2499
inf = 10 ** 18
arr = [[inf for _ in range(2500)] for _ in range(n)]
(c, d) = coin[0]
for i in range(2500):
	if i <= s:
		arr[0][i] = 0
	elif i - c < 0:
		arr[0][i] = arr[0][0] + d
	else:
		arr[0][i] = arr[0][i - c] + d
now = {0}
for _ in range(100):
	last = now
	now = set()
	for x in last:
		for y in road[x]:
			(v, a, b) = y
			now.add(v)
			(c, d) = coin[v]
			for i in range(2500):
				if i + a < 2500:
					arr[v][i] = min(arr[v][i], arr[x][i + a] + b)
			for i in range(2500):
				if i - c < 0:
					arr[v][i] = min(arr[v][i], arr[v][0] + d)
				else:
					arr[v][i] = min(arr[v][i], arr[v][i - c] + d)
for ii in range(1, n):
	print(arr[ii][0])


import sys

def input():
	return sys.stdin.readline().strip()

def mapint():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 9)
(N, M, S) = mapint()
S = min(S, N * 50)
query = [[[] for _ in range(N * 50 + 1)] for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = mapint()
	for coin in range(a, N * 50 + 1):
		query[u - 1][coin].append((v - 1, a, b))
		query[v - 1][coin].append((u - 1, a, b))
for i in range(N):
	(c, d) = mapint()
	for coin in range(N * 50 + 1):
		query[i][coin].append((i, -c, d))
inf = 10 ** 18
dp = [[inf] * (N * 50 + 1) for _ in range(N)]
dp[0][0] = 0
import heapq
queue = [(0, 0, S)]
checked = [0] * N
cnt = 0
while queue:
	(t, now, coin) = heapq.heappop(queue)
	if cnt == N:
		break
	if not checked[now]:
		checked[now] = 1
		cnt += 1
	qlis = query[now][coin]
	for (nx, a, b) in qlis:
		if 0 <= coin - a:
			coin = min(coin, N * 50 + a)
			if t + b < dp[nx][coin - a]:
				dp[nx][coin - a] = t + b
				heapq.heappush(queue, (t + b, nx, coin - a))
for i in range(1, N):
	print(min(dp[i]))


import sys
from heapq import heappop, heappush
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

def solve():
	(N, M, S) = map(int, rl().split())
	init_s = min(2500, S)
	graph = [[] for _ in range(N)]
	for _ in range(M):
		(u, v, a, b) = map(int, rl().split())
		(u, v) = (u - 1, v - 1)
		graph[u].append((v, a, b))
		graph[v].append((u, a, b))
	(C, D) = ([0] * N, [0] * N)
	for i in range(N):
		(C[i], D[i]) = map(int, rl().split())
	costs = [[10 ** 18] * 2501 for _ in range(N)]
	costs[0][init_s] = 0
	que = [(0, 0, init_s)]
	while que:
		(t, cur, s) = heappop(que)
		self_roop_s = min(s + C[cur], 2500)
		self_roop_t = t + D[cur]
		if self_roop_t < costs[cur][self_roop_s]:
			costs[cur][self_roop_s] = self_roop_t
			heappush(que, (self_roop_t, cur, self_roop_s))
		for (child, s_cost, t_cost) in graph[cur]:
			if s < s_cost:
				continue
			nt = t + t_cost
			ns = s - s_cost
			if nt < costs[child][ns]:
				costs[child][ns] = nt
				heappush(que, (nt, child, ns))
	for costs_i in costs[1:]:
		print(min(costs_i))
solve()


from collections import deque
(N, M, S) = map(int, input().split())
city = [[] for i in range(N)]
for i in range(M):
	(u, v, a, b) = map(int, input().split())
	city[u - 1].append([v - 1, a, b])
	city[v - 1].append([u - 1, a, b])
ex = [[] for i in range(N)]
for i in range(N):
	(c, d) = map(int, input().split())
	ex[i] = [c, d]
MCOIN = 5000
cost = [[float('inf')] * (MCOIN + 500) for i in range(N)]
cost[0][min(MCOIN, S)] = 0
queue = deque([[0, min(MCOIN, S)]])
while queue:
	(p, m) = queue.popleft()
	if m < MCOIN and cost[p][m + ex[p][0]] > cost[p][m] + ex[p][1]:
		queue.append([p, m + ex[p][0]])
		cost[p][m + ex[p][0]] = cost[p][m] + ex[p][1]
	for (v, a, b) in city[p]:
		if m >= a and cost[v][m - a] > cost[p][m] + b:
			queue.append([v, m - a])
			cost[v][m - a] = cost[p][m] + b
for i in cost[1:]:
	print(min(i))


INF = 1000000000000000
MAX = 50 * 50
(n, m, s) = map(int, input().split())
(u, v, a, b, c, d) = ([0] * m, [0] * m, [0] * m, [0] * m, [0] * n, [0] * n)
for i in range(m):
	(u[i], v[i], a[i], b[i]) = map(int, input().split())
	u[i] -= 1
	v[i] -= 1
for i in range(n):
	(c[i], d[i]) = map(int, input().split())
dp = [[INF] * (MAX + 1) for _ in range(n)]
dp[0][min(MAX, s)] = 0
updated = True
while updated:
	updated = False
	for i in range(n):
		for j in range(MAX + 1):
			dest = min(MAX, j + c[i])
			if dp[i][j] + d[i] < dp[i][dest]:
				updated = True
				dp[i][dest] = dp[i][j] + d[i]
	for i in range(m):
		for j in range(a[i], MAX + 1):
			if dp[u[i]][j] + b[i] < dp[v[i]][j - a[i]]:
				updated = True
				dp[v[i]][j - a[i]] = dp[u[i]][j] + b[i]
			if dp[v[i]][j] + b[i] < dp[u[i]][j - a[i]]:
				updated = True
				dp[u[i]][j - a[i]] = dp[v[i]][j] + b[i]
for i in range(1, n):
	print(min(dp[i]))


from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(N, M, S) = map(int, input().split())
S = min(2500, S)
PATH = [[] for _ in range(N + 1)]
CHANGES = [None] * (N + 1)
for _ in range(M):
	(U, V, A, B) = map(int, input().split())
	PATH[U].append((V, A, B))
	PATH[V].append((U, A, B))
for i in range(N):
	(C, D) = map(int, input().split())
	CHANGES[i + 1] = (C, D)
Q = []
INF = float('inf')
TIME = [[INF] * 2501 for _ in range(N + 1)]
USED = [[False] * 2501 for _ in range(N + 1)]
Q.append((0, 1, S))
TIME[1][S] = 0
while Q:
	(t, u, g) = heappop(Q)
	if g < 2500:
		(c, d) = CHANGES[u]
		ng = min(g + c, 2500)
		nt = t + d
		if nt < TIME[u][ng]:
			TIME[u][ng] = nt
			heappush(Q, (nt, u, ng))
	for (v, a, b) in PATH[u]:
		if g < a:
			continue
		ng = g - a
		nt = t + b
		if nt < TIME[v][ng]:
			TIME[v][ng] = nt
			heappush(Q, (nt, v, ng))
ANS = [min(x) for x in TIME[2:]]
print('\n'.join(map(str, ANS)))


from scipy.sparse import *
((n, m, s, *D), *t) = [map(int, t.split()) for t in open(0)]
x = 51
r = range(0, x ** 3, x)
for (u, v, a, b) in t[:m]:
	for i in r:
		D += (i + a * x + u, i + v, b, i + a * x + v, i + u, b)
i = 0
for (c, d) in t[m:]:
	i += 1
	for j in r:
		D += (j + i, j + c * x + i, d)
d = csgraph.dijkstra(csr_matrix((D[2::3], (D[::3], D[1::3])), [j * 2] * 2), 1, min(j, s * x) + 1)
for i in range(2, n + 1):
	print(int(min(d[i::x])))


import heapq

def main():
	(N, M, S) = map(int, input().split())
	money_max = 50 * N
	S = min(S, money_max)
	dp = [[float('inf')] * (money_max + 1) for _ in range(N)]
	dp[0][S] = 0
	G = [[] for _ in range(N)]
	exchange = [None] * N
	for _ in range(M):
		(u, v, a, b) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		G[u].append([v, a, b])
		G[v].append([u, a, b])
	for i in range(N):
		(c, d) = map(int, input().split())
		exchange[i] = [c, d]
	q = []
	heapq.heapify(q)
	heapq.heappush(q, [0, 0, S])
	while 0 < len(q):
		(pre_time, idx, s) = heapq.heappop(q)
		if dp[idx][s] < pre_time:
			continue
		ex = min(s + exchange[idx][0], money_max)
		if dp[idx][s] + exchange[idx][1] < dp[idx][ex]:
			dp[idx][ex] = dp[idx][s] + exchange[idx][1]
			heapq.heappush(q, [dp[idx][ex], idx, ex])
		for (to, money, time) in G[idx]:
			if money <= s:
				if dp[idx][s] + time < dp[to][s - money]:
					dp[to][s - money] = dp[idx][s] + time
					heapq.heappush(q, [dp[to][s - money], to, s - money])
	for i in range(1, N):
		print(min(dp[i]))
main()


import heapq
import sys

def dijkstra(e, dist, s, used):
	q = []
	heapq.heappush(q, (0, 0, s))
	while q:
		(d, x, m) = heapq.heappop(q)
		if not used[x][m]:
			continue
		dist[x][m] = d
		used[x][m] = False
		for (cost, newx, silver) in e[x][m]:
			if used[newx][silver]:
				heapq.heappush(q, (dist[x][m] + cost, newx, silver))
	return dist

def main():
	input = sys.stdin.readline
	(n, m, s) = map(int, input().split())
	if s > 2500:
		s = 2500
	edge = [[[] for i in range(2501)] for _ in range(n)]
	for _ in range(m):
		(u, v, a, b) = map(int, input().split())
		u -= 1
		v -= 1
		for j in range(a, 2501):
			edge[u][j].append((b, v, j - a))
			edge[v][j].append((b, u, j - a))
	for i in range(n):
		(c, d) = map(int, input().split())
		for j in range(2501 - c):
			edge[i][j].append((d, i, j + c))
	dist = [[10 ** 18] * 2501 for _ in range(n)]
	used = [[True] * 2501 for _ in range(n)]
	dist = dijkstra(edge, dist, s, used)
	for i in range(1, n):
		print(min(dist[i]))
main()


import heapq

def main():
	(N, M, S) = map(int, input().split())
	maxS = 50 * (N - 1)
	cost = [[] for _ in range(N)]
	for _ in range(M):
		(U, V, A, B) = map(int, input().split())
		U = U - 1
		V = V - 1
		cost[U].append((A, B, V))
		cost[V].append((A, B, U))
	for i in range(N):
		cost[i].sort()
	r = []
	for _ in range(N):
		(C, D) = map(int, input().split())
		r.append((C, D))
	time = [-1] * N
	money = [-1] * N
	used = set()
	cities = N
	q = [(0, S, 0)]
	count = 0
	while cities:
		count += 1
		(t, s, ci) = heapq.heappop(q)
		if (s, ci) in used or money[ci] >= s:
			continue
		used.add((s, ci))
		if time[ci] == -1:
			time[ci] = t
			money[ci] = s
			cities -= 1
		for (a, b, v) in cost[ci]:
			if s < a:
				break
			if (s - a, v) not in used and money[v] < s - a:
				heapq.heappush(q, (t + b, s - a, v))
		if s != maxS:
			(c, d) = r[ci]
			m = cost[ci][0][0]
			k = max(1, (m - s + c - 1) // c)
			if (s + c, ci) not in used:
				heapq.heappush(q, (t + d * k, min(s + c * k, maxS), ci))
	for i in time[1:]:
		print(i)
main()


from heapq import heappush, heappop
inf = float('inf')

def dijkstra(graph: list, node: int, start: int) -> list:
	dist = [inf] * node
	dist[start] = 0
	heap = [(0, start)]
	while heap:
		(cost, thisNode) = heappop(heap)
		for (NextCost, NextNode) in graph[thisNode]:
			dist_cand = dist[thisNode] + NextCost
			if dist_cand < dist[NextNode]:
				dist[NextNode] = dist_cand
				heappush(heap, (dist[NextNode], NextNode))
	return dist
(N, M, S) = map(int, input().split())
graph = [[] for i in range(2501 * N)]
for i in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for s in range(a, 2501):
		graph[2501 * u + s].append([b, 2501 * v + s - a])
		graph[2501 * v + s].append([b, 2501 * u + s - a])
for i in range(N):
	(c, d) = map(int, input().split())
	for s in range(2500):
		graph[2501 * i + s].append([d, 2501 * i + min(2500, s + c)])
dist = dijkstra(graph, 2501 * N, min(2500, S))
ans = [inf] * N
for i in range(N):
	for s in range(2501):
		ans[i] = min(ans[i], dist[2501 * i + s])
for i in range(1, N):
	print(ans[i])


from heapq import heappop, heappush
(N, M, S) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
Y = [list(map(int, input().split())) for _ in range(N)]
lim = 2501
graph = [[] for _ in range((N + 1) * lim)]
for (u, v, a, b) in X:
	for n in range(a, lim):
		graph[u * lim + n].append((v * lim + (n - a), b))
		graph[v * lim + n].append((u * lim + (n - a), b))
for (n, (c, d)) in enumerate(Y):
	for x in range(lim - 1):
		graph[(n + 1) * lim + x].append(((n + 1) * lim + min(lim - 1, x + c), d))
INF = 10 ** 20
start = lim + min(S, lim - 1)
dist = [INF] * ((N + 1) * lim + 1)
dist[start] = 0
pq = []
heappush(pq, (0, start))
while pq:
	(_, u) = heappop(pq)
	for (v, c) in graph[u]:
		if dist[v] > dist[u] + c:
			dist[v] = dist[u] + c
			heappush(pq, (dist[v], v))
ans = []
for i in range(2, N + 1):
	ans.append(min(dist[i * lim:i * lim + lim]))
print(*ans, sep='\n')


from heapq import heappush, heappop

def main():
	(N, M, S) = list(map(int, input().split()))
	G = [[] for _ in range(N)]
	for _ in range(M):
		(u, v, a, b) = list(map(int, input().split()))
		u -= 1
		v -= 1
		G[u].append((v, a, b))
		G[v].append((u, a, b))
	CD = [list(map(int, input().split())) for _ in range(N)]
	distance = [[1 << 62] * 2501 for _ in range(N)]
	q = [(0, 0, min(S, 2500))]
	distance[0][min(S, 2500)] = 0
	while q:
		(d, v, vs) = heappop(q)
		if distance[v][vs] != d:
			continue
		(vc, vd) = CD[v]
		ud = d + vd
		us = vs + vc
		if us > 2500:
			us = 2500
		if distance[v][us] > ud:
			distance[v][us] = ud
			heappush(q, (ud, v, us))
		for (u, fee, b) in G[v]:
			if fee > vs:
				continue
			ud = d + b
			us = vs - fee
			if us > 2500:
				us = 2500
			if distance[u][us] > ud:
				distance[u][us] = ud
				heappush(q, (ud, u, us))
	print('\n'.join((str(min(d)) for d in distance[1:])))
main()


def main():
	import heapq
	(n, m, s) = map(int, input().split())
	edges = [[] for _ in range(n)]
	max_cost = 0
	for _ in range(m):
		(from_, to, cost, time) = map(int, input().split())
		edges[from_ - 1].append((to - 1, cost, time))
		edges[to - 1].append((from_ - 1, cost, time))
		if cost > max_cost:
			max_cost = cost
	banks = []
	for i in range(n):
		(coin, time) = map(int, input().split())
		banks.append((coin, time))
	max_coin = max_cost * (n - 1)
	if s > max_coin:
		s = max_coin
	INF = float('INF')
	DP = [[INF] * (max_coin + 1) for _ in range(n)]
	DP[0][s] = 0

	def push_todo(node, coin, time):
		if coin < 0:
			return
		if time >= DP[node][coin]:
			return
		heapq.heappush(todo, (time, node, coin))
		DP[node][coin] = time

	def charge(node, current_coin, current_time):
		(coin, time) = banks[node]
		new_coin = current_coin + coin
		if new_coin > max_coin:
			new_coin = max_coin
		push_todo(node, new_coin, current_time + time)
	todo = [(0, 0, s)]
	while todo:
		(current_time, node, current_coin) = heapq.heappop(todo)
		if current_time > DP[node][current_coin]:
			continue
		charge(node, current_coin, current_time)
		for (to, cost, time) in edges[node]:
			push_todo(to, current_coin - cost, current_time + time)
	for node in range(1, n):
		print(min(DP[node]))

def __starting_point():
	main()
__starting_point()


from heapq import *
(n, m, s) = map(int, input().split())
s = min([s, 50 * n])
tree = [[] for _i in range(n + 1)]
for _i in range(m):
	(u, v, a, b) = map(int, input().split())
	tree[u].append([v, a, b])
	tree[v].append([u, a, b])
cd = [[0, 0]]
for _i in range(n):
	cd.append(list(map(int, input().split())))
dp = [[float('inf') for _i in range(50 * n + 1)] for _j in range(n + 1)]
hq = [[0, 1, s]]
dp[1][s] = 0
heapify(hq)
while hq:
	(t, p, g) = heappop(hq)
	if g + cd[p][0] <= 50 * n:
		(x, y) = (t + cd[p][1], min([g + cd[p][0], 50 * n]))
		if dp[p][y] > x:
			dp[p][y] = x
			heappush(hq, [x, p, y])
	for (x, y, z) in tree[p]:
		if g - y >= 0 and dp[x][g - y] > t + z:
			dp[x][g - y] = t + z
			heappush(hq, [t + z, x, g - y])
for i in dp[2:]:
	print(min(i))


(N, M, S) = map(int, input().split())
edges = [[] for _ in range(2500 * 50 + 100)]

def indexer(city, coin):
	return 50 * coin + city
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for scoin in range(a, 2501):
		edges[indexer(u, scoin)].append((b, indexer(v, scoin - a)))
		edges[indexer(v, scoin)].append((b, indexer(u, scoin - a)))
for i in range(N):
	(c, d) = map(int, input().split())
	for scoin in range(c, 2501):
		edges[indexer(i, scoin - c)].append((d, indexer(i, scoin)))

def dijkstra(s, n, edges):
	import heapq
	dist = [float('inf')] * n
	fixed = [False] * n
	dist[s] = 0
	fixed[s] = True
	priority_que = []
	for e in edges[s]:
		heapq.heappush(priority_que, e)
	while len(priority_que):
		edge = heapq.heappop(priority_que)
		if fixed[edge[1]]:
			continue
		v = edge[1]
		dist[v] = edge[0]
		fixed[v] = True
		for ne in edges[v]:
			heapq.heappush(priority_que, (ne[0] + dist[v], ne[1]))
	return dist
d = dijkstra(indexer(0, min(2500, S)), 2500 * 50 + 100, edges)
for i in range(1, N):
	ans = float('inf')
	for j in range(2501):
		ans = min(ans, d[indexer(i, j)])
	print(ans)


def solve():
	import sys
	input = sys.stdin.readline
	(N, M, S) = map(int, input().split())
	UVAB = [tuple(map(int, input().split())) for i in range(M)]
	CD = [tuple(map(int, input().split())) for i in range(N)]
	es = [[] for _ in range(N)]
	for (u, v, a, b) in UVAB:
		(u, v) = (u - 1, v - 1)
		es[u].append((v, a, b))
		es[v].append((u, a, b))
	INF = float('inf')
	times = [INF] * (2501 * N)
	start = min(2500, S) * N
	times[start] = 0
	hq = [start]
	ans = [-1] * N
	ans[0] = 0
	reached = 0
	import heapq
	heapq.heapify(hq)
	while hq:
		x = heapq.heappop(hq)
		(t, v) = divmod(x, N * 2501)
		(s, i) = divmod(v, N)
		if ans[i] < 0:
			ans[i] = t
			reached += 1
			if reached == N - 1:
				break
		for (to, a, b) in es[i]:
			if a > s:
				continue
			nv = (s - a) * N + to
			if times[nv] <= t + b:
				continue
			times[nv] = t + b
			heapq.heappush(hq, (t + b) * N * 2501 + nv)
		ns = s
		nt = times[v]
		while ns <= 2500:
			ns += CD[i][0]
			nt += CD[i][1]
			nv = min(2500, ns) * N + i
			if times[nv] <= nt:
				break
			times[nv] = nt
			heapq.heappush(hq, nt * N * 2501 + nv)
	print(*ans[1:], sep='\n')
solve()


import math
import heapq
(N, M, S) = map(int, input().split())
Us = [0] * M
Vs = [0] * M
As = [0] * M
Bs = [0] * M
for i in range(M):
	(Us[i], Vs[i], As[i], Bs[i]) = map(int, input().split())
	Us[i] -= 1
	Vs[i] -= 1
V = {}
Ns = max(As) * N
Nv = N * (Ns + 1)
cnt = 0
for i in range(N):
	for ns in range(Ns + 1):
		V[i, ns] = cnt
		cnt += 1
G = [[] for _ in range(Nv)]
if S > Ns:
	S = Ns
for _ in range(M):
	u = Us.pop()
	v = Vs.pop()
	a = As.pop()
	b = Bs.pop()
	for i in range(Ns + 1):
		ns_s = Ns - i
		ns_g = ns_s - a
		if ns_g >= 0:
			G[V[u, ns_s]].append((V[v, ns_g], b))
			G[V[v, ns_s]].append((V[u, ns_g], b))
for i in range(N):
	(c, d) = map(int, input().split())
	for j in range(Ns):
		ns_s = j
		ns_g = j + c
		if ns_g > Ns:
			ns_g = Ns
		G[V[i, ns_s]].append((V[i, ns_g], d))
D = [math.inf] * Nv
q = []
s = V[0, S]
D[s] = 0
heapq.heappush(q, (0, s))
while len(q) > 0:
	(p_cost, p_v) = heapq.heappop(q)
	if D[p_v] < p_cost:
		continue
	for (e_to, e_cost) in G[p_v]:
		if D[e_to] > D[p_v] + e_cost:
			D[e_to] = D[p_v] + e_cost
			heapq.heappush(q, (D[e_to], e_to))
for i in range(1, N):
	ans = min([D[i * (Ns + 1) + v] for v in range(Ns + 1)])
	print(ans)


import sys
input = sys.stdin.readline
import heapq

def dijkstra(edge, start):
	n = len(edge)
	dist = [float('inf')] * n
	dist[start] = 0
	que = [(0, start)]
	while que:
		(d, v) = heapq.heappop(que)
		if dist[v] < d:
			continue
		for (nv, nd) in edge[v]:
			if dist[nv] > d + nd:
				dist[nv] = d + nd
				heapq.heappush(que, (dist[nv], nv))
	return dist
(n, m, s) = map(int, input().split())
G = [[] for _ in range(n)]
if s >= 2500:
	for _ in range(m):
		(u, v, a, b) = map(int, input().split())
		u -= 1
		v -= 1
		G[u].append((v, b))
		G[v].append((u, b))
	L = dijkstra(G, 0)
else:
	for _ in range(m):
		(u, v, a, b) = map(int, input().split())
		u -= 1
		v -= 1
		G[u].append((v, a, b))
		G[v].append((u, a, b))
	CD = [list(map(int, input().split())) for _ in range(n)]
	edge = [[] for _ in range(n * 2500)]
	for i in range(n):
		(c, d) = CD[i]
		for k in range(2500):
			for (v, a, b) in G[i]:
				if k >= a:
					edge[2500 * i + k].append((2500 * v + (k - a), b))
			if k + c < 2500:
				edge[2500 * i + k].append((2500 * i + (k + c), d))
	dist = dijkstra(edge, s)
	L = [0] * n
	for i in range(n):
		L[i] = min(dist[2500 * i:2500 * (i + 1)])
print(*L[1:], sep='\n')


import sys
from heapq import heappop, heappush
(n, m, ss) = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
	(u, v, a, b) = map(int, line.split())
	u -= 1
	v -= 1
	links[u].add((v, a, b))
	links[v].add((u, a, b))
	aaa.append(a)
exchanges = []
for line in lines[m:]:
	(c, d) = map(int, line.split())
	exchanges.append((c, d))
req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n
q = [(0, ss, 0)]
visited = set()
fixed = 0
while q:
	(t, s, v) = heappop(q)
	if (s, v) in visited or ans_silver[v] >= s:
		continue
	visited.add((s, v))
	if ans[v] == INF:
		ans[v] = t
		ans_silver[v] = s
		fixed += 1
		if fixed == n:
			break
	for (u, a, b) in links[v]:
		if s < a:
			continue
		ns = s - a
		nt = t + b
		if (ns, u) in visited or ans_silver[u] >= ns:
			continue
		heappush(q, (nt, ns, u))
	(c, d) = exchanges[v]
	ns = s + c
	if ns <= req and (ns, v) not in visited:
		heappush(q, (t + d, ns, v))
print('\n'.join(map(str, ans[1:])))


import sys
input = sys.stdin.readline
(N, M, S) = map(int, input().split())
E = [[] for i in range(N + 1)]
for i in range(M):
	(u, v, a, b) = map(int, input().split())
	E[u].append((v, a, b))
	E[v].append((u, a, b))
C = [(0, 0)] + [tuple(map(int, input().split())) for i in range(N)]
DP = [[1 << 60] * 5001 for i in range(51)]
import heapq
Q = [(0, min(S, 5000), 1)]
DP[1][min(S, 5000)] = 0
while Q:
	(time, money, town) = heapq.heappop(Q)
	for (to, pmoney, ptime) in E[town]:
		if money >= pmoney and DP[to][money - pmoney] > time + ptime:
			DP[to][money - pmoney] = time + ptime
			heapq.heappush(Q, (time + ptime, money - pmoney, to))
	if DP[town][min(money + C[town][0], 5000)] > time + C[town][1]:
		DP[town][min(money + C[town][0], 5000)] = time + C[town][1]
		heapq.heappush(Q, (time + C[town][1], min(money + C[town][0], 5000), town))
for i in range(2, N + 1):
	print(min(DP[i]))


import sys
from heapq import *
input = sys.stdin.readline

def main():
	(N, M, S) = map(int, input().split())
	edges = [[] for _ in range(N)]
	for _ in range(M):
		(u, v, a, b) = map(int, input().split())
		u -= 1
		v -= 1
		edges[u].append((v, a, b))
		edges[v].append((u, a, b))
	ex = [tuple(map(int, input().split())) for _ in range(N)]
	M = 2500
	dist = [[2 ** 60] * M for _ in range(N)]
	if S >= M:
		S = M - 1
	dist[0][S] = 0
	q = [(0, S, 0)]
	while q:
		(cost, sil, u) = heappop(q)
		if dist[u][sil] < cost:
			continue
		if sil + ex[u][0] < M and cost + ex[u][1] < dist[u][sil + ex[u][0]]:
			dist[u][sil + ex[u][0]] = cost + ex[u][1]
			heappush(q, (dist[u][sil + ex[u][0]], sil + ex[u][0], u))
		for (v, a, b) in edges[u]:
			if sil >= a and cost + b < dist[v][sil - a]:
				dist[v][sil - a] = cost + b
				heappush(q, (dist[v][sil - a], sil - a, v))
	for t in range(1, N):
		print(min(dist[t]))
main()


from heapq import *
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	inf = 10 ** 16
	(n, m, s) = MI()
	to = [[] for _ in range(n)]
	for _ in range(m):
		(u, v, a, b) = MI()
		to[u - 1].append((v - 1, a, b))
		to[v - 1].append((u - 1, a, b))
	cd = LLI(n)
	dp = [[inf] * 3005 for _ in range(n)]
	hp = []
	heappush(hp, (0, min(s, 3000), 0))
	dp[0][min(s, 3000)] = 0
	while hp:
		(t, g, u) = heappop(hp)
		if dp[u][g] < t:
			continue
		(c, d) = cd[u]
		if g + c < 3000:
			if dp[u][g + c] > t + d:
				dp[u][g + c] = t + d
				heappush(hp, (t + d, g + c, u))
		elif dp[u][3000] > t + d:
			dp[u][3000] = t + d
			heappush(hp, (t + d, 3000, u))
		for (v, a, b) in to[u]:
			if g - a < 0:
				continue
			if dp[v][g - a] <= t + b:
				continue
			dp[v][g - a] = t + b
			heappush(hp, (t + b, g - a, v))
	for u in range(1, n):
		print(min(dp[u]))
main()


import heapq
import sys
input = sys.stdin.readline
inf = 10 ** 13
(N, M, S) = map(int, input().split())
data = [[] for _ in range(N)]
sumA = 0
for i in range(M):
	(U, V, A, B) = map(int, input().split())
	sumA += A
	U -= 1
	V -= 1
	data[U].append((B, V, A))
	data[V].append((B, U, A))
P = sumA
C = [0] * N
D = [0] * N
for i in range(N):
	(C[i], D[i]) = map(int, input().split())
dist = [[inf] * (P + 1) for _ in range(N)]
q = [(0, 0, min(S, P))]
heapq.heapify(q)
while q:
	v = heapq.heappop(q)
	if v[0] >= dist[v[1]][v[2]]:
		continue
	dist[v[1]][v[2]] = v[0]
	if v[2] + C[v[1]] <= P:
		if dist[v[1]][v[2] + C[v[1]]] == inf:
			heapq.heappush(q, (v[0] + D[v[1]], v[1], v[2] + C[v[1]]))
	for x in data[v[1]]:
		if x[2] > v[2]:
			continue
		if dist[x[1]][v[2] - x[2]] == inf:
			heapq.heappush(q, (v[0] + x[0], x[1], v[2] - x[2]))
for i in range(1, N):
	print(min(dist[i]))


import heapq as hq
(N, M, S) = list(map(int, input().split()))
E = [[] for _ in range(N)]
for _ in range(M):
	(u, v, a, b) = list(map(int, input().split()))
	E[u - 1].append([v - 1, a, b])
	E[v - 1].append([u - 1, a, b])
C = []
for _ in range(N):
	C.append(list(map(int, input().split())))
MAXYEN = 50 * N
dp = [[1e+18 for i in range(MAXYEN + 5)] for _ in range(N)]
S = min(MAXYEN, S)
dp[0][S] = 0
Q = []
hq.heapify(Q)
hq.heappush(Q, [0, 0, S])
while len(Q) > 0:
	(nowt, nowi, nowm) = hq.heappop(Q)
	for e in E[nowi]:
		(to_i, costm, costt) = e
		if nowm - costm < 0:
			continue
		if dp[to_i][nowm - costm] > dp[nowi][nowm] + costt:
			dp[to_i][nowm - costm] = dp[nowi][nowm] + costt
			hq.heappush(Q, [dp[nowi][nowm] + costt, to_i, nowm - costm])
	(getm, costt) = C[nowi]
	targetm = min(MAXYEN, nowm + getm)
	if dp[nowi][targetm] > dp[nowi][nowm] + costt:
		dp[nowi][targetm] = dp[nowi][nowm] + costt
		hq.heappush(Q, [dp[nowi][targetm], nowi, targetm])
for i in range(1, N):
	print(min(dp[i]))


from heapq import heapify, heappush as hpush, heappop as hpop
(N, M, S) = map(int, input().split())
k = 2451
X = [[] for _ in range(N * k)]
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	for i in range(a, k):
		X[u * k + i].append([v * k + i - a, b])
		X[v * k + i].append([u * k + i - a, b])
for i in range(N):
	(c, d) = map(int, input().split())
	for j in range(k - 1):
		X[i * k + j].append([i * k + min(j + c, k - 1), d])

def dijkstra(n, E, i0=0):
	h = [[0, i0]]
	D = [-1] * n
	done = [0] * n
	D[i0] = 0
	while h:
		(d, i) = hpop(h)
		done[i] = 1
		for (j, w) in E[i]:
			nd = d + w
			if D[j] < 0 or D[j] > nd:
				if done[j] == 0:
					hpush(h, [nd, j])
					D[j] = nd
	return D
D = dijkstra(N * k, X, min(S, k - 1))
print(*[min(D[i * k:(i + 1) * k]) for i in range(N)][1:], sep='\n')


(n, m, s) = map(int, input().split())
edges = [[] for _ in range(n)]
amax = 0
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	edges[u - 1].append((v - 1, a, b))
	edges[v - 1].append((u - 1, a, b))
	amax = max(a, amax)
lcoins = amax * (n - 1)
cost = []
time = []
for _ in range(n):
	(c, d) = map(int, input().split())
	cost.append(c)
	time.append(d)
from heapq import *
INF = 1 << 61
M = 2500
if s >= M:
	s = M - 1
dist = [[INF] * M for _ in range(n)]
dist[0][s] = 0
q = [(0, s, 0)]
while q:
	(dv, num, v) = heappop(q)
	if dist[v][num] < dv:
		continue
	if num + cost[v] < M and dv + time[v] < dist[v][num + cost[v]]:
		dist[v][num + cost[v]] = dv + time[v]
		heappush(q, (dv + time[v], num + cost[v], v))
	for (next, a, b) in edges[v]:
		if num >= a and dv + b < dist[next][num - a]:
			dist[next][num - a] = dv + b
			heappush(q, (dv + b, num - a, next))
for i in range(1, n):
	print(min(dist[i]))


import heapq
(n, m, s) = map(int, input().split())
s = min(s, 2499)
UV = [[] for _ in range(n)]
A_cost = []
B_dist = []
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	UV[u].append((v, i))
	UV[v].append((u, i))
	A_cost.append(a)
	B_dist.append(b)
C_income = []
D_dist = []
for _ in range(n):
	(c, d) = map(int, input().split())
	C_income.append(c)
	D_dist.append(d)
NV = 2500 * n
edges = [[] for _ in range(NV)]
for i in range(n):
	c = C_income[i]
	d = D_dist[i]
	for j in range(2500 - c):
		edges[2500 * i + j].append((d, 2500 * i + j + c))
for i in range(n):
	for (j, k) in UV[i]:
		a = A_cost[k]
		b = B_dist[k]
		for x in range(2500 - a):
			edges[2500 * i + x + a].append((b, 2500 * j + x))

def dijkstra(init_v):
	next_v = [(0, init_v)]
	INF = 10 ** 18
	dist = [INF] * NV
	dist[init_v] = 0
	while next_v:
		(d, v) = heapq.heappop(next_v)
		if dist[v] < d:
			continue
		for (d, v2) in edges[v]:
			if dist[v2] <= dist[v] + d:
				continue
			dist[v2] = dist[v] + d
			heapq.heappush(next_v, (dist[v2], v2))
	return dist
INF = 10 ** 18
dist = dijkstra(s)
for i in range(1, n):
	ans = INF
	for j in range(2500):
		ans = min(ans, dist[2500 * i + j])
	print(ans)


import sys
from heapq import *
I = sys.stdin.readlines()
(N, M, S) = map(int, I[0].split())
S = min(S, 2499)
G = [[] for i in range(2500 * N)]
(u, v, a, b) = (0, 0, 0, 0)
for i in range(M):
	(u, v, a, b) = map(int, I[i + 1].split())
	(u, v) = (u - 1, v - 1)
	for j in range(a, 2500):
		G[u + j * N].append((v + (j - a) * N, b))
		G[v + j * N].append((u + (j - a) * N, b))
for i in range(N):
	(a, b) = map(int, I[M + i + 1].split())
	for j in range(a, 2500):
		G[i + (j - a) * N].append((i + j * N, b))
D = [0] * (2500 * N)
INF = 10 ** 15

def ijk(s):
	global D, INF, G
	for i in range(len(G)):
		D[i] = INF
	D[s] = 0
	Q = []
	heapify(Q)
	heappush(Q, (0, s))
	(p, v, e) = (0, 0, 0)
	while len(Q):
		p = heappop(Q)
		v = p[1]
		if D[v] < p[0]:
			continue
		for i in range(len(G[v])):
			e = G[v][i]
			if D[e[0]] > D[v] + e[1]:
				D[e[0]] = D[v] + e[1]
				heappush(Q, (D[e[0]], e[0]))
ijk(S * N)
for i in range(1, N):
	print(min(D[i::N]))


import heapq
(N, M, S) = map(int, input().split(' '))
edges = {i: [] for i in range(2501 * N - 1)}
for i in range(M):
	(U, V, A, B) = map(int, input().split(' '))
	edges[U - 1].append((V - 1, A, B))
	edges[V - 1].append((U - 1, A, B))
exchange_edges = {}
for i in range(N):
	(C, D) = map(int, input().split(' '))
	exchange_edges[i] = (C, D)
dist = [[-1 for _ in range(2501)] for _ in range(N)]
que = []
heapq.heappush(que, (0, 0, min(S, 2500)))
while que:
	(time, now, s) = heapq.heappop(que)
	if dist[now][s] != -1:
		continue
	dist[now][s] = time
	for (to, a, b) in edges[now]:
		if a > s or dist[to][s - a] != -1:
			continue
		heapq.heappush(que, (time + b, to, s - a))
	(silv, t) = exchange_edges[now]
	if s + silv <= 2500 and dist[now][silv + s] == -1:
		heapq.heappush(que, (time + t, now, s + silv))
for i in range(1, N):
	print(min(dist[i]))


from heapq import heappop, heappush
(n, m, s) = map(int, input().split())
edges = [[[] for _ in range(2501)] for _ in range(n)]
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	for x in range(2501):
		if x - a >= 0:
			edges[u - 1][x].append((b, v - 1, x - a))
			edges[v - 1][x].append((b, u - 1, x - a))
for i in range(n):
	(c, d) = map(int, input().split())
	for x in range(2500):
		edges[i][x].append((d, i, min(2500, x + c)))
inf = 1000000000000000.0
d = [[inf for _ in range(2501)] for _ in range(n)]
s = min(s, 2500)

def dijkstra():
	que = []
	d[0][s] = 0
	heappush(que, (0, 0, s))
	while len(que):
		(dist, city, coins) = heappop(que)
		if d[city][coins] < dist:
			continue
		for (cost, to_city, to_coins) in edges[city][coins]:
			if d[to_city][to_coins] > dist + cost:
				d[to_city][to_coins] = dist + cost
				heappush(que, (d[to_city][to_coins], to_city, to_coins))
dijkstra()
for i in range(1, n):
	print(min(d[i]))


from heapq import heappop, heappush, heapify
MAX_MONEY = 2500
INF = float('inf')
(n, m, s) = map(int, input().split())
s = min(s, MAX_MONEY)
graph = [[] for _ in range(n)]
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	graph[u].append((v, a, b))
	graph[v].append((u, a, b))
cd = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[INF] * (MAX_MONEY + 10) for _ in range(n)]
dp[0][s] = 0
q = [(0, 0, s)]
while q:
	(dist, v, money) = heappop(q)
	if dp[v][money] < dist:
		continue
	for (nv, fare, cost) in graph[v]:
		nm = money - fare
		if nm < 0:
			continue
		if dp[nv][nm] > dp[v][money] + cost:
			dp[nv][nm] = dp[v][money] + cost
			heappush(q, (dp[nv][nm], nv, nm))
	nm = min(money + cd[v][0], MAX_MONEY)
	if dp[v][nm] > dp[v][money] + cd[v][1]:
		dp[v][nm] = dp[v][money] + cd[v][1]
		heappush(q, (dp[v][nm], v, nm))
for i in range(1, n):
	print(min(dp[i]))


import math
import heapq
(n, m, s) = map(int, input().split())
road = []
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	road.append([u, v, a, b])
change = []
for i in range(n):
	(c, d) = map(int, input().split())
	change.append([c, d])
tree = [[] for _ in range(n + 1)]
for i in range(m):
	r = road[i]
	tree[r[0]].append([r[0], r[1], r[2], r[3]])
	tree[r[1]].append([r[1], r[0], r[2], r[3]])
least_cost = [[] for _ in range(n + 1)]
for l in range(n + 1):
	least_cost[l] = [math.inf] * 2501
queue = []

def dijakstra(q):
	while q != []:
		hwd = heapq.heappop(q)
		if least_cost[hwd[1]][hwd[2]] > hwd[0]:
			least_cost[hwd[1]][hwd[2]] = hwd[0]
			for node in tree[hwd[1]]:
				if hwd[2] - node[2] >= 0:
					heapq.heappush(q, (hwd[0] + node[3], node[1], hwd[2] - node[2]))
			if hwd[2] + change[hwd[1] - 1][0] <= 2500:
				heapq.heappush(q, (hwd[0] + change[hwd[1] - 1][1], hwd[1], hwd[2] + change[hwd[1] - 1][0]))
	return least_cost
if s > 2500:
	s = 2500
queue.append((0, 1, s))
ans = dijakstra(queue)
for i in range(2, n + 1):
	print(min(ans[i]))


import sys
sys.setrecursionlimit(10 ** 6)
(n, m, s) = map(int, input().split())
g = [list(map(int, input().split())) for i in range(m)]
c = [list(map(int, input().split())) for i in range(n)]
x = 2501
gg = [[] for i in range(n * x)]
for i in range(n):
	for j in range(x - 1):
		y = j + c[i][0]
		if y >= x - 1:
			y = x - 1
		gg[i * x + j].append((i * x + y, c[i][1]))
for i in range(1, x):
	for (u, v, a, b) in g:
		u -= 1
		v -= 1
		if i - a >= 0:
			gg[v * x + i].append((u * x + i - a, b))
			gg[u * x + i].append((v * x + i - a, b))
from heapq import heappush, heappop

def dijkstra(edges, size, source):
	distance = [float('inf')] * size
	distance[source] = 0
	visited = [False] * size
	pq = []
	heappush(pq, (0, source))
	while pq:
		(dist_v, v) = heappop(pq)
		visited[v] = True
		for (u, weight) in edges[v]:
			if not visited[u]:
				new_dist = dist_v + weight
				if distance[u] > new_dist:
					distance[u] = new_dist
					heappush(pq, (new_dist, u))
	return distance
s = min(s, 2500)
ans = dijkstra(gg, n * x, s)
for i in range(1, n):
	print(min(ans[x * i:x * (i + 1)]))


(n, m, s) = map(int, input().split())
uvab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(n)]
chg = 10 ** 5
from collections import defaultdict
link = defaultdict(list)
for node in range(n):
	(cmai, dmin) = cd[node]
	for frm in range(2600):
		link[node * chg + frm].append([node * chg + frm + cmai, dmin])
for i in range(m):
	(u, v, a, b) = uvab[i]
	u -= 1
	v -= 1
	for sil in range(2600):
		link[u * chg + sil + a].append([v * chg + sil, b])
		link[v * chg + sil + a].append([u * chg + sil, b])
from heapq import heappush, heappop, heappushpop, heapify
from collections import defaultdict

def dks(g, start):
	INF = float('inf')
	visited = set()
	hq = []
	heappush(hq, (0, start))
	cost = defaultdict(lambda : float('inf'))
	while hq:
		(shortest, i) = heappop(hq)
		if i in visited:
			continue
		visited.add(i)
		cost[i] = shortest
		for (j, t) in g[i]:
			if j in visited:
				continue
			heappush(hq, (shortest + t, j))
	return cost
f_sil = min(s, 2555)
res = dks(link, f_sil)
for node in range(1, n):
	ans = float('inf')
	for sil in range(2600):
		ans = min(ans, res[node * chg + sil])
	print(ans)


from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
(N, M, S) = map(int, input().split())
d = defaultdict(list)
e = defaultdict(int)
for _ in range(M):
	(U, V, A, B) = map(int, input().split())
	d[U].append((A, B, V))
	d[V].append((A, B, U))
for i in range(1, N + 1):
	(C, D) = map(int, input().split())
	e[i] = (C, D)
dist = defaultdict(lambda : 10 ** 30)
ans = defaultdict(lambda : 10 ** 30)
source = (1, S)
dist[source] = 0
q = [(0, source)]
while q:
	(cost, (s, nokori)) = heappop(q)
	ns = (s, nokori)
	(u, v) = e[s]
	if dist[ns] < cost:
		continue
	if nokori > 2500:
		nokori = 2500
	else:
		n_nokori = nokori + u
		n_cost = v
		if n_nokori > 2500:
			n_nokori = 2500
		nt = (s, n_nokori)
		if dist[nt] > dist[ns] + n_cost:
			dist[nt] = dist[ns] + n_cost
			heappush(q, (dist[nt], nt))
	for (a, b, t) in d[s]:
		n_nokori = nokori - a
		n_cost = b
		nt = (t, n_nokori)
		if n_nokori < 0:
			continue
		if dist[nt] > dist[ns] + n_cost:
			dist[nt] = dist[ns] + n_cost
			heappush(q, (dist[nt], nt))
for ((s, _), v) in dist.items():
	ans[s] = min(ans[s], v)
for i in range(2, N + 1):
	print(ans[i])


from heapq import *

def dijkstra(sta):
	dist = [10 ** 18] * (N * 2510)
	dist[sta] = 0
	pq = []
	heappush(pq, (dist[sta], sta))
	while pq:
		(d, v) = heappop(pq)
		if dist[v] < d:
			continue
		for (nv, w) in G[v]:
			if dist[nv] > dist[v] + w:
				dist[nv] = dist[v] + w
				heappush(pq, (dist[nv], nv))
	return dist
(N, M, S) = map(int, input().split())
serial = [[0] * 2510 for _ in range(N)]
c = 0
for i in range(N):
	for j in range(2510):
		serial[i][j] = c
		c += 1
G = [[] for _ in range(N * 2510)]
for _ in range(M):
	(U, V, A, B) = map(int, input().split())
	U -= 1
	V -= 1
	for i in range(A, 2510):
		G[serial[U][i]].append((serial[V][i - A], B))
		G[serial[V][i]].append((serial[U][i - A], B))
for v in range(N):
	(C, D) = map(int, input().split())
	for i in range(2510):
		if i + C >= 2510:
			break
		G[serial[v][i]].append((serial[v][i + C], D))
dist = dijkstra(serial[0][min(S, 2509)])
for i in range(1, N):
	ans = 10 ** 18
	for j in range(2510):
		ans = min(ans, dist[serial[i][j]])
	print(ans)


[print(min(m[i])[0]) for h in [__import__('heapq')] for (a, d, r, n, x) in [(h.heappush, h.heappop, range, lambda : map(int, input().split()), list.append)] for (N, M, S) in [n()] for (g, q) in [([[] for _ in r(N)], [(0, S, 0)])] for L in [max((A for _ in r(M) for (U, V, A, B) in [n()] if not (x(g[U - 1], (V - 1, A, B)) or x(g[V - 1], (U - 1, A, B))))) * (N - 1)] for m in [[[[2 ** 64] for _ in r(L + 1)] for _ in r(N)]] for _ in [[[x(g[i], (i, -C, D)) for i in r(N) for (C, D) in [n()]], [[[_ for (s, v, i) in [d(q)] for _ in [[a(q, (s + c, j, t)) for (t, p, c) in g[i] for j in [min(L, v - p)] for y in [m[t][j]] if v >= p and s + c < y[0] and (not (y.clear() or x(y, s + c)))]] if not (x(l, None) if q else l.clear())]] for l in [[None]] for _ in l]]] for i in r(1, N)]


import heapq
MAX = 2500
(n, m, s) = map(int, input().split())
s = min(s, MAX)
edge = [[] for i in range(n)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	edge[u - 1].append([v - 1, a, b])
	edge[v - 1].append([u - 1, a, b])
for i in range(n):
	(c, d) = map(int, input().split())
	edge[i].append([i, -c, d])
dp = [[float('inf')] * (MAX + 1) for _ in range(n)]
dp[0][s] = 0
edgelist = [(0, 0, s)]
while edgelist:
	(time, node, silver) = heapq.heappop(edgelist)
	for (to, silver_cost, time_cost) in edge[node]:
		res_silver = min(silver - silver_cost, MAX)
		if res_silver < 0:
			continue
		dp_next_value = time + time_cost
		if dp[to][res_silver] <= dp_next_value:
			continue
		dp[to][res_silver] = dp_next_value
		heapq.heappush(edgelist, (dp_next_value, to, res_silver))
print(*[min(d) for d in dp[1:]], sep='\n')


import heapq
dp = {}
hq = []
(N, M, S) = map(int, input().split())
MAX_S = (N - 1) * 50
INF = 10 ** 18
S = min(S, MAX_S)
for i in range(1, N + 1):
	dp[i] = {}
	for j in range(MAX_S + 1):
		dp[i][j] = INF
uv = {}
for i in range(N):
	uv[i + 1] = []
for i in range(M):
	(U, V, A, B) = map(int, input().split())
	uv[U].append((V, A, B))
	uv[V].append((U, A, B))
c = {}
d = {}
for i in range(N):
	(C, D) = map(int, input().split())
	c[i + 1] = C
	d[i + 1] = D

def q_push(v, money, time):
	if money < 0:
		return
	if dp[v][money] <= time:
		return
	dp[v][money] = time
	heapq.heappush(hq, (time, v, money))
q_push(1, S, 0)
while hq:
	(now_t, now_v, now_m) = heapq.heappop(hq)
	if dp[now_v][now_m] != now_t:
		continue
	new_money = min(now_m + c[now_v], MAX_S)
	q_push(now_v, new_money, now_t + d[now_v])
	for (next_v, next_a, next_b) in uv[now_v]:
		q_push(next_v, now_m - next_a, now_t + next_b)
for i in range(2, N + 1):
	ans = INF
	for j in range(0, MAX_S + 1):
		ans = min(ans, dp[i][j])
	print(ans)


from heapq import heappop, heappush
(n, m, s) = map(int, input().split())
g = [[] for i in range(n)]
x = 0
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	g[u - 1].append([v - 1, a, b])
	g[v - 1].append([u - 1, a, b])
	x = max(x, a)
for i in range(n):
	(c, d) = map(int, input().split())
	g[i].append([i, -c, d])
x *= n - 1
t = [[2 ** 64 for i in range(x + 1)] for i in range(n)]
q = []
heappush(q, (0, 0, s))
while q:
	(a, b, c) = heappop(q)
	for (i, j, h) in g[b]:
		if c >= j and a + h < t[i][min(x, c - j)]:
			t[i][min(x, c - j)] = a + h
			heappush(q, (a + h, i, c - j))
for i in range(1, n):
	print(min(t[i]))


import sys
input = sys.stdin.readline
import heapq

def dijkstra(Route, v, start):
	Dist = [float('inf')] * v
	Dist[start] = 0
	Visited = [False] * v
	hq = [(0, start)]
	while hq:
		(dist, fr) = heapq.heappop(hq)
		Visited[fr] = True
		for (to, cost) in Route[fr]:
			if not Visited[to] and Dist[to] > dist + cost:
				Dist[to] = dist + cost
				heapq.heappush(hq, (Dist[to], to))
	return Dist

def main():
	(n, m, s) = map(int, input().split())
	s_max = 2500
	Edges = [[] for _ in range(n * s_max)]
	for _ in range(m):
		(u, v, cost, time) = map(int, input().split())
		u -= 1
		v -= 1
		for i in range(cost, s_max):
			Edges[u * s_max + i].append((v * s_max + i - cost, time))
			Edges[v * s_max + i].append((u * s_max + i - cost, time))
	Change = [None] * n
	for i in range(n):
		(change, time) = map(int, input().split())
		for j in range(s_max - change):
			Edges[i * s_max + j].append((i * s_max + j + change, time))
	Dist = dijkstra(Edges, n * s_max, min(s, s_max - 1))
	for i in range(1, n):
		print(min(Dist[i * s_max:(i + 1) * s_max]))
main()


import heapq
(n, m, s) = map(int, input().split())
lst_graph = [list(map(int, input().split())) for _ in range(m)]
lst_cd = [list(map(int, input().split())) for _ in range(n)]
graph = [[] for _ in range(2501 * n)]

def f(x, c):
	if c >= 2500:
		c = 2500
	return (x - 1) * 2501 + c
for i in range(m):
	(u, v, a, b) = lst_graph[i]
	for c in range(2501):
		if c >= a:
			graph[f(u, c)].append((b, f(v, c - a)))
			graph[f(v, c)].append((b, f(u, c - a)))
for i in range(1, n + 1):
	(x, time) = lst_cd[i - 1]
	for c in range(2500):
		graph[f(i, c)].append((time, f(i, c + x)))

def dijkstra_heap(s, edge):
	d = [float('inf')] * (2501 * n)
	used = [True] * (2501 * n)
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, e)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, (e[0] + d[v], e[1]))
	return d
ans = dijkstra_heap(f(1, s), graph)
for i in range(1, n):
	print(min(ans[2501 * i:2501 * i + 2501]))


import sys
readline = sys.stdin.readline
(N, M, S) = map(int, readline().split())
from heapq import heappop as hpp, heappush as hp

def dijkstra(N, s, Edge):
	inf = 10 ** 18
	dist = [inf] * N
	dist[s] = 0
	Q = [(0, s)]
	while Q:
		(dn, vn) = hpp(Q)
		if dn > dist[vn]:
			continue
		for (df, vf) in Edge[vn]:
			if dist[vn] + df < dist[vf]:
				dist[vf] = dist[vn] + df
				hp(Q, (dn + df, vf))
	return dist
geta = 2451
Edge = [[] for _ in range(N * geta)]
S = min(S, geta - 1)
for m in range(M):
	(u, v, a, b) = map(int, readline().split())
	u -= 1
	v -= 1
	for mon in range(a, geta):
		Edge[u * geta + mon].append((b, v * geta + (mon - a)))
		Edge[v * geta + mon].append((b, u * geta + (mon - a)))
for n in range(N):
	(c, d) = map(int, readline().split())
	for mon in range(geta):
		Edge[n * geta + mon].append((d, n * geta + min(geta - 1, mon + c)))
dist = dijkstra(N * geta, S, Edge)
INF = 10 ** 18
ans = [INF] * N
for i in range(N * geta):
	ans[i // geta] = min(ans[i // geta], dist[i])
print('\n'.join(map(str, ans[1:])))


def main():
	import sys
	sys.setrecursionlimit(10 ** 9)
	input = sys.stdin.readline
	from heapq import heappush, heappop
	(N, M, S) = map(int, input().split())
	S = min(S, 2500)
	graph = [[] for _ in range(N)]
	for (u, v, a, b) in (map(int, input().split()) for _ in range(M)):
		graph[u - 1].append((v - 1, a, b))
		graph[v - 1].append((u - 1, a, b))
	for (i, (c, d)) in enumerate((map(int, input().split()) for _ in range(N))):
		graph[i].append((i, -c, d))
	hq = [(0, 0, S)]
	INF = 10 ** 18
	dp = [[INF] * 2501 for _ in range(N)]
	dp[0][S] = 0
	while hq:
		(time, v, silver) = heappop(hq)
		if dp[v][silver] < time:
			continue
		for (dest, a, b) in graph[v]:
			next_s = silver - a if silver - a < 2500 else 2500
			if next_s < 0 or dp[dest][next_s] <= time + b:
				continue
			for i in range(next_s, -1, -1):
				if dp[dest][i] > time + b:
					dp[dest][i] = time + b
				else:
					break
			heappush(hq, (time + b, dest, next_s))
	print(*(min(dp[i]) for i in range(1, N)), sep='\n')
main()


from heapq import *
(n, m, s) = map(int, input().split())
c = [0] * n
d = [0] * n
g = [[] for i in range(n)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append((v, a, b))
	g[v].append((u, a, b))
for i in range(n):
	(c[i], d[i]) = map(int, input().split())
flag = 0
lasttime = [[10 ** 15] * 2501 for i in range(n)]
lasttime[0][min(2500, s)] = 0
mintimes = [10 ** 15] * n
hp = [(0, min(2500, s), 0)]
while flag != (1 << n) - 1:
	(time, silver, node) = heappop(hp)
	flag = flag | 1 << node
	mintimes[node] = min(mintimes[node], time)
	for (atnode, costmoney, costtime) in g[node]:
		(nexttime, nextsilver) = (time + costtime, silver - costmoney)
		if costmoney <= silver and lasttime[atnode][nextsilver] > nexttime:
			heappush(hp, (nexttime, nextsilver, atnode))
			lasttime[atnode][nextsilver] = min(lasttime[atnode][nextsilver], nexttime)
	(nexttime, nextsilver) = (time + d[node], min(silver + c[node], 2500))
	if silver != 2500 and lasttime[node][nextsilver] > nexttime:
		heappush(hp, (nexttime, min(silver + c[node], 2500), node))
		lasttime[node][nextsilver] = min(lasttime[node][nextsilver], nexttime)
print(*mintimes[1:], sep='\n')


from collections import defaultdict
from heapq import heappop, heappush, heapify
import sys
input = sys.stdin.readline
(N, M, S) = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
(U, V, A, B) = zip(*UVAB)
mc = max(A) * M
g = defaultdict(list)
for (u, v, a, b) in UVAB:
	for i in range(a, mc + 1):
		g[u, i].append(((v, i - a), b))
		g[v, i].append(((u, i - a), b))
CD = [[0, 0]] + [list(map(int, input().split())) for i in range(N)]
(C, D) = zip(*CD)
C = [min(c, mc) for c in C]
for i in range(1, N + 1):
	for c in range(mc + 1 - C[i]):
		g[i, c].append(((i, c + C[i]), D[i]))
S = min(S, mc)
dq = [(0, S, 1)]
ans = [[10 ** 15 for j in range(mc + 1)] for i in range(N + 1)]
while dq:
	(t, w, v) = heappop(dq)
	if ans[v][w] <= t:
		continue
	for i in range(w + 1):
		ans[v][i] = min(t, ans[v][i])
	for ((nv, nw), nt) in g[v, w]:
		if ans[nv][nw] > t + nt:
			heappush(dq, (t + nt, nw, nv))
for i in range(2, N + 1):
	print(min(ans[i]))


from heapq import heappush, heappop

def resolve():
	INF = float('inf')
	maxMoney = 2502

	def Dijkstra(g):
		ans = {}
		dp = [[INF] * (maxMoney + 1) for _ in range(N)]
		hq = []
		heappush(hq, (0, 0, min(S, maxMoney)))
		while hq:
			(t, v, s) = heappop(hq)
			if t > dp[v][s]:
				continue
			if v not in ans:
				ans[v] = t
				if len(ans) == N:
					break
			if s < maxMoney:
				(c, d) = CD[v]
				new_s = min(s + c, maxMoney)
				new_t = t + d
				if new_t < dp[v][new_s]:
					dp[v][new_s] = new_t
					heappush(hq, (new_t, v, new_s))
			for (nv, cost, time) in G[v]:
				if s < cost:
					continue
				new_s = s - cost
				new_t = t + time
				if new_t < dp[nv][new_s]:
					dp[nv][new_s] = new_t
					heappush(hq, (new_t, nv, new_s))
		return ans
	(N, M, S) = list(map(int, input().split()))
	G = [[] for _ in range(N)]
	for _ in range(M):
		(u, v, coin, tm) = list(map(int, input().split()))
		(u, v) = (u - 1, v - 1)
		G[u].append((v, coin, tm))
		G[v].append((u, coin, tm))
	CD = [list(map(int, input().split())) for _ in range(N)]
	ans = Dijkstra(G)
	for i in range(1, N):
		print(ans[i])

def __starting_point():
	resolve()
__starting_point()


INF = 10 ** 30
from heapq import heappush, heappop, heapify

def dijkstra(G, coin, s, n):
	que = [(0, [coin, s])]
	dist = [[INF] * n for i in range(2501)]
	dist[coin][s] = 0
	while que:
		(mincost, co) = heappop(que)
		(nowc, nowv) = (co[0], co[1])
		if mincost > dist[nowc][nowv]:
			continue
		for (v, c, x) in G[nowc][nowv]:
			if dist[nowc][nowv] + c < dist[x][v]:
				dist[x][v] = dist[nowc][nowv] + c
				heappush(que, (dist[x][v], [x, v]))
	return dist
(N, M, S) = map(int, input().split())
if S >= 2500:
	S = 2500
G = [[[] for i in range(N)] for i in range(2501)]
for i in range(M):
	(u, v, a, b) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	for i in range(2501):
		if i - a >= 0:
			G[i][u].append([v, b, i - a])
			G[i][v].append([u, b, i - a])
for i in range(N):
	(c, d) = map(int, input().split())
	for j in range(2500):
		if j + c <= 2500:
			G[j][i].append([i, d, j + c])
dist = dijkstra(G, S, 0, N)
for i in range(1, N):
	res = 10 ** 30
	for j in range(2501):
		res = min(res, dist[j][i])
	print(res)


from heapq import *
import sys
input = sys.stdin.buffer.readline
(n, m, s) = map(int, input().split())
lim = 2510
di = [[float('inf')] * lim for _ in range(n)]
di[0][min(s, lim - 1)] = 0
con = [[] for _ in range(n)]
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	con[u - 1].append((v - 1, a, b))
	con[v - 1].append((u - 1, a, b))
q = [(0, min(s, lim - 1), 0)]
cd = [list(map(int, input().split())) for _ in range(n)]
while q:
	(time, have, cur) = heappop(q)
	if di[cur][have] < time:
		continue
	(c, d) = cd[cur]
	if have + c < lim and di[cur][have + c] > time + d:
		di[cur][have + c] = time + d
		heappush(q, (time + d, have + c, cur))
	for (nxt, dh, dt) in con[cur]:
		if have >= dh and di[nxt][have - dh] > time + dt:
			di[nxt][have - dh] = time + dt
			heappush(q, (time + dt, have - dh, nxt))
for p in di[1:]:
	print(min(p))


from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
(N, M, S, *I) = map(int, open(0).read().split())
(UVAB, CD) = (I[:4 * M], I[4 * M:])
(R, C, V) = ([], [], [])
for (u, v, a, b) in zip(*[iter(UVAB)] * 4):
	for i in range(2501 - a):
		R += [(i + a) * 51 + u, (i + a) * 51 + v]
		C += [i * 51 + v, i * 51 + u]
		V += [b, b]
for (i, (c, d)) in enumerate(zip(*[iter(CD)] * 2), 1):
	for j in range(2501 - c):
		R.append(j * 51 + i)
		C.append((j + c) * 51 + i)
		V.append(d)
D = dijkstra(csr_matrix((V, (R, C)), [2500 * 60] * 2), indices=min(2500, S) * 51 + 1)
for i in range(2, N + 1):
	print(int(D[i::51].min()))


import sys
input = lambda : sys.stdin.readline().rstrip()
import heapq
(n, m, s) = map(int, input().split())
s = min(s, 2499)
E = []
for _ in range(m):
	E.append(tuple(map(int, input().split())))
CD = []
for _ in range(n):
	CD.append(tuple(map(int, input().split())))
nn = n * 2500
edge = [[] for i in range(nn)]
for (u, v, a, b) in E:
	u -= 1
	v -= 1
	for i in range(a, 2500):
		edge[u * 2500 + i].append(b * 10 ** 6 + v * 2500 + i - a)
		edge[v * 2500 + i].append(b * 10 ** 6 + u * 2500 + i - a)
for i in range(n):
	(c, d) = CD[i]
	for j in range(2500):
		if j + c < 2500:
			edge[i * 2500 + j].append(d * 10 ** 6 + i * 2500 + j + c)

def dijkstra_heap(s):
	d = [float('inf')] * nn
	used = [True] * nn
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, e)
	while edgelist:
		minedge = heapq.heappop(edgelist)
		minedge_cost = minedge // 10 ** 6
		minedge_v = minedge % 10 ** 6
		if not used[minedge_v]:
			continue
		d[minedge_v] = minedge_cost
		used[minedge_v] = False
		for e in edge[minedge_v]:
			e_cost = e // 10 ** 6
			e_v = e % 10 ** 6
			if used[e_v]:
				heapq.heappush(edgelist, e + minedge_cost * 10 ** 6)
	return d
D = dijkstra_heap(s)
for i in range(1, n):
	ans = D[i * 2500]
	for j in range(1, 2500):
		ans = min(ans, D[i * 2500 + j])
	print(ans)


import heapq
(city_num, road_num, init_silver) = map(int, input().split())
MAX_COST = 2500
init_silver = min(MAX_COST, init_silver)
G = [[] for _ in range(city_num)]
for _ in range(road_num):
	(A, B, cost, time_cost) = map(int, input().split())
	(A, B) = (A - 1, B - 1)
	G[B].append([A, cost, time_cost])
	G[A].append([B, cost, time_cost])
for n in range(city_num):
	(cost, time_cost) = map(int, input().split())
	G[n].append([n, -cost, time_cost])
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(city_num)]
dp[0][init_silver] = 0
hq = [(0, 0, init_silver)]
while hq:
	(time, node, silver) = heapq.heappop(hq)
	for (to, silver_cost, time_cost) in G[node]:
		remain = min(silver - silver_cost, MAX_COST)
		if remain < 0:
			continue
		dp_next_value = time + time_cost
		if dp[to][remain] <= dp_next_value:
			continue
		dp[to][remain] = dp_next_value
		heapq.heappush(hq, (dp_next_value, to, remain))
print(*[min(d) for d in dp[1:]], sep='\n')


from queue import PriorityQueue
from collections import defaultdict
from heapq import heappush, heappop
(n, m, s) = map(int, input().split())
graph = defaultdict(dict)
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	graph[u][v] = (a, b)
	graph[v][u] = (a, b)
town = [None] * (n + 1)
for i in range(n):
	(c, d) = map(int, input().split())
	town[i + 1] = (c, d)
if s >= 2501:
	s = 2501
x = (1, s)
cost = 0
visit = set()
heap = []
heappush(heap, (cost, x))
ans = [None] * (n + 1)
check = 0
while len(heap) > 0:
	(cost, x) = heappop(heap)
	if x in visit:
		continue
	visit.add(x)
	(p, m) = x
	if ans[p] is None:
		ans[p] = cost
		check += 1
		if check >= n:
			break
	(c, d) = town[p]
	if m <= 2501:
		heappush(heap, (cost + d, (p, m + c)))
	for (q, edge) in graph[p].items():
		(a, b) = edge
		if m - a >= 0:
			heappush(heap, (cost + b, (q, m - a)))
for i in range(2, n + 1):
	print(ans[i])


import sys
from heapq import heappush, heappop
import numpy as np

def input():
	return sys.stdin.readline().rstrip()

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def main():

	def dijkstra(s):

		def push(v, s, x):
			if s < 0:
				return
			if dist[v, s] <= x:
				return
			dist[v, s] = x
			heappush(que, (x, v, s))
		inf = 10 ** 18
		dist = np.full((n, MAX_S + 1), inf, dtype=int)
		que = []
		push(0, s, 0)
		while que:
			(x, v, s) = heappop(que)
			if dist[v, s] < x:
				continue
			ns = min(s + c[v], MAX_S)
			push(v, ns, x + d[v])
			for (nv, a, b) in adj[v]:
				push(nv, s - a, x + b)
		return np.min(dist, axis=1)
	(n, m, s) = mi()
	adj = [[] for i in range(n)]
	MAX_S = 0
	for i in range(m):
		(u, v, a, b) = mi()
		u -= 1
		v -= 1
		adj[u].append((v, a, b))
		adj[v].append((u, a, b))
		MAX_S = max(MAX_S, a)
	MAX_S *= n - 1
	s = min(s, MAX_S)
	(c, d) = ([0] * n, [0] * n)
	for i in range(n):
		(c[i], d[i]) = mi()
	ans = dijkstra(s)
	print(*ans[1:], sep='\n')

def __starting_point():
	main()
__starting_point()


import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)
INF = 1e+19
MAX_V = 50
MAX_S = MAX_V * 50 + 5
(n, m, s) = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	g[u - 1].append((v - 1, a, b))
	g[v - 1].append((u - 1, a, b))
cd = [list(map(int, input().split())) for _ in range(n)]
dp = [[INF] * (MAX_S + 5) for _ in range(MAX_V)]
s = min(s, MAX_S)
q = []

def push(v, s, x):
	if s < 0:
		return
	if dp[v][s] <= x:
		return
	dp[v][s] = x
	heapq.heappush(q, (x, s, v))
push(0, s, 0)
while q:
	(x, s, v) = heapq.heappop(q)
	if dp[v][s] != x:
		continue
	ns = min(s + cd[v][0], MAX_S)
	push(v, ns, x + cd[v][1])
	for (to, a, b) in g[v]:
		push(to, s - a, x + b)
for i in range(1, n):
	print(min(dp[i][:MAX_S + 5]))


from heapq import heappush, heappop
(N, M, S) = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
cd = [tuple(map(int, input().split())) for _ in range(N)]
INF = 10 ** 15
mod = 55
mmax = sum([edges[i][2] for i in range(M)])
if S > mmax:
	S = mmax
G = [{} for _ in range((mmax + 1) * mod + N + 1)]
for i in range(M):
	(u, v, a, b) = edges[i]
	for p in range(a, mmax + 1):
		G[u + p * mod][v + (p - a) * mod] = b
		G[v + p * mod][u + (p - a) * mod] = b
for i in range(N):
	(c, d) = cd[i]
	for p in range(mmax + 1 - c):
		G[i + 1 + p * mod][i + 1 + (p + c) * mod] = d

def dijkstra(start=0):
	d = [INF for i in range(len(G) + 1)]
	d[start] = 0
	que = []
	heappush(que, (0, start))
	while len(que):
		p = heappop(que)
		v = p[1]
		if d[v] < p[0]:
			continue
		for u in G[v].keys():
			if d[u] > d[v] + G[v][u]:
				d[u] = d[v] + G[v][u]
				heappush(que, (d[u], u))
	return d
start = 1 + S * mod
d = dijkstra(start)
ans = [INF] * (N + 1)
for i in range(2, len(G) + 1):
	v = i % mod
	if v > N or v < 2:
		continue
	ans[v] = min(ans[v], d[i])
print(*ans[2:])


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
(N, M, S) = map(int, input().split())
e = dd(list)
for _ in range(M):
	(u, v, a, b) = map(int, input().split())
	u -= 1
	v -= 1
	for x in range(a, 2501):
		e[N * x + u].append((N * (x - a) + v, b))
		e[N * x + v].append((N * (x - a) + u, b))
for i in range(N):
	(c, d) = map(int, input().split())
	for x in range(2501):
		e[N * x + i].append((N * min(2500, x + c) + i, d))
import heapq

class dijkstra:

	def __init__(self, n, e):
		self.e = e
		self.n = n

	def path(self, s, t):
		d = [float('inf')] * (self.n + 1)
		vis = set()
		d[s] = 0
		h = [s]
		while len(h):
			v = heapq.heappop(h)
			v1 = v % 10 ** 6
			v0 = v // 10 ** 6
			if v1 in vis:
				continue
			vis.add(v1)
			for p in self.e[v1]:
				d[p[0]] = min(d[p[0]], d[v1] + p[1])
				if p[0] in vis:
					continue
				heapq.heappush(h, d[p[0]] * 10 ** 6 + p[0])
		return d
dij = dijkstra(2501 * N, e)
p = dij.path(min(S, 2500) * N, 0)
for i in range(1, N):
	res = float('inf')
	for j in range(2501):
		res = min(res, p[i + N * j])
	print(res)


(n, m, s) = map(int, input().split())
rail = [[] for _ in range(n)]
fare = [[] for _ in range(n)]
time = [[] for _ in range(n)]
rate = []
TIME = []
for _ in range(m):
	(i, j, k, l) = map(int, input().split())
	i -= 1
	j -= 1
	rail[i].append(j)
	rail[j].append(i)
	fare[i].append(k)
	fare[j].append(k)
	time[i].append(l)
	time[j].append(l)
for _ in range(n):
	(i, j) = map(int, input().split())
	rate.append(i)
	TIME.append(j)
limit = [max(i) for i in fare]
limit = max(limit) * n
if s >= limit:
	s = limit - 1
dp = [[float('inf')] * limit for _ in range(n)]
import heapq
candidate = [(0, 0, s)]
heapq.heapify(candidate)
ans = [-1] * n
todo = n
while todo > 0:
	(i, j, k) = heapq.heappop(candidate)
	if dp[j][k] != float('inf'):
		continue
	dp[j][k] = i
	if ans[j] == -1:
		ans[j] = i
		todo -= 1
	for l in range(len(rail[j])):
		if fare[j][l] <= k and dp[rail[j][l]][k - fare[j][l]] == float('inf'):
			heapq.heappush(candidate, (i + time[j][l], rail[j][l], k - fare[j][l]))
	if k < limit - 1:
		heapq.heappush(candidate, (i + TIME[j], j, min([k + rate[j], limit - 1])))
for i in range(1, n):
	print(ans[i])


max_s = 2500
(n, m, s) = map(int, input().split())
s = min(s, max_s)
conv = lambda i, j: i * 10000 + j
G = [[] for i in range(conv(n - 1, max_s) + 1)]
for i in range(m):
	(u, v, a, b) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	for j in range(max_s + 1):
		if j - a >= 0:
			G[conv(u, j)].append((conv(v, j - a), b))
			G[conv(v, j)].append((conv(u, j - a), b))
for i in range(n):
	(c, d) = map(int, input().split())
	for j in range(max_s + 1):
		if j + c > max_s:
			break
		G[conv(i, j)].append((conv(i, j + c), d))
from heapq import heappush, heappop

def dijkstra(G, start):
	n = len(G)
	dist = [float('inf')] * n
	visited = set()
	heap = [(0, start)]
	while heap and len(visited) != n:
		(d, cur) = heappop(heap)
		if cur in visited:
			continue
		visited.add(cur)
		dist[cur] = d
		for (to, cost) in G[cur]:
			if to not in visited:
				heappush(heap, (d + cost, to))
	return dist
dist = dijkstra(G, conv(0, s))
for i in range(1, n):
	cost = min(dist[conv(i, 0):conv(i, max_s) + 1])
	print(cost)


import heapq
(N, M, S) = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(N)]
for i in range(M):
	uvab[i][0] -= 1
	uvab[i][1] -= 1
railways = [[] for _ in range(N)]
max_a = 0
for (u, v, a, b) in uvab:
	railways[u].append((v, a, b))
	railways[v].append((u, a, b))
	max_a = max(max_a, a)
del uvab
max_silver = max_a * (N - 1)
ans = [-1] * N
d = dict()
d[S, 0] = 0
Q = [(0, S, 0)]
sum_reached = 0
reached = [False] * N
while Q:
	(t, sv, st) = heapq.heappop(Q)
	if not reached[st]:
		ans[st] = t
		reached[st] = True
		sum_reached += 1
		if sum_reached == N:
			break
	new_key = (min(max_silver, sv + cd[st][0]), st)
	new_value = t + cd[st][1]
	if new_key not in d or d[new_key] > new_value:
		d[new_key] = t + cd[st][1]
		heapq.heappush(Q, (new_value, *new_key))
	for (dist, a, b) in railways[st]:
		if sv >= a:
			new_key = (sv - a, dist)
			new_value = t + b
			if new_key not in d or d[new_key] > new_value:
				d[new_key] = new_value
				heapq.heappush(Q, (new_value, *new_key))
print(*ans[1:], sep='\n')


from heapq import heappush, heappop
infi = 10 ** 20
(n, m, s) = map(int, input().split())
s = min(s, n * 50)
edges = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v, a, b) = map(int, input().split())
	edges[v].append((u, a, b))
	edges[u].append((v, a, b))
exchange = [(0, 0)] * (n + 1)
for edge_num in range(1, n + 1):
	(c, d) = map(int, input().split())
	exchange[edge_num] = (c, d)
start = 1
dp = [[infi] * (n * 50 + 1) for _ in range(n + 1)]

def dijkstra(edges, start, s, dp):
	dp[start][s] = 0
	edgelist = []
	heappush(edgelist, (0, s, start))
	while edgelist:
		(nowtime, nowmoney, nowedge) = heappop(edgelist)
		if dp[nowedge][nowmoney] != nowtime:
			continue
		(deltamoney, deltatime) = exchange[nowedge]
		nextmoney = min(nowmoney + deltamoney, n * 50)
		nexttime = nowtime + deltatime
		if dp[nowedge][nextmoney] > nexttime:
			dp[nowedge][nextmoney] = nexttime
			heappush(edgelist, (nexttime, nextmoney, nowedge))
		for (v, vmoney, vtime) in edges[nowedge]:
			nexttime = nowtime + vtime
			nextmoney = nowmoney - vmoney
			if nextmoney < 0:
				continue
			if dp[v][nextmoney] > nexttime:
				dp[v][nextmoney] = nexttime
				heappush(edgelist, (nexttime, nextmoney, v))
	return dp
time = dijkstra(edges, start, s, dp)
ans = [infi] * (n + 1)
for i in range(1, n + 1):
	for j in range(n * 50 + 1):
		ans[i] = min(ans[i], dp[i][j])
print(*ans[2:n + 1], sep='\n')


(N, M, S) = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
(C, D) = zip(*[list(map(int, input().split())) for i in range(N)])
c = [[] for i in range(N)]
A = [[] for i in range(N)]
B = [[] for i in range(N)]
for (u, v, a, b) in UVAB:
	c[u - 1].append(v - 1)
	c[v - 1].append(u - 1)
	A[u - 1].append(a)
	A[v - 1].append(a)
	B[u - 1].append(b)
	B[v - 1].append(b)
inf = 10 ** 20
from heapq import heappop, heappush
X = 50 * (N - 1)

def dij(p, s):
	d = [[inf] * (X + 1) for i in range(N)]
	d[p][s] = 0
	q = []
	heappush(q, (0, (p, s)))
	while q:
		(t, (p, s)) = heappop(q)
		for i in range(1, (X + 1 - s) // C[p]):
			if X < s + i * C[p] or d[p][s + i * C[p]] <= d[p][s] + i * D[p]:
				break
			d[p][s + i * C[p]] = d[p][s] + i * D[p]
			heappush(q, (d[p][s] + i * D[p], (p, s + i * C[p])))
		for (j, n) in enumerate(c[p]):
			if 0 <= s - A[p][j] and d[n][s - A[p][j]] > d[p][s] + B[p][j]:
				d[n][s - A[p][j]] = d[p][s] + B[p][j]
				heappush(q, (d[n][s - A[p][j]], (n, s - A[p][j])))
	return d
d = dij(0, min(S, X))
print(*[min(x) for x in d[1:]], sep='\n')


import sys

def input():
	return sys.stdin.readline().strip()

def mapint():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 9)
(N, M, S) = mapint()
graph = [{} for _ in range(N)]
for _ in range(M):
	(u, v, a, t) = mapint()
	graph[u - 1][v - 1] = (a, t)
	graph[v - 1][u - 1] = (a, t)
change = [list(mapint()) for _ in range(N)]
from heapq import heappop, heappush
Q = [(0, min(2500, S), 0)]
dist = [[10 ** 18] * 2501 for _ in range(N)]
dist[0][min(2500, S)] = 0
while Q:
	(t, s, v) = heappop(Q)
	(rate, change_time) = change[v]
	if s < 2500 and dist[v][min(2500, s + rate)] > t + change_time:
		dist[v][min(2500, s + rate)] = t + change_time
		heappush(Q, (t + change_time, min(2500, s + rate), v))
	for nx in graph[v].keys():
		(nx_s, nx_t) = graph[v][nx]
		if nx_s <= s and dist[nx][s - nx_s] > t + nx_t:
			dist[nx][s - nx_s] = t + nx_t
			heappush(Q, (t + nx_t, s - nx_s, nx))
for i in range(1, N):
	print(min(dist[i]))


import collections
import heapq
INF = 10 ** 18
MAX_S = 50 * 50 + 5

def Z():
	return int(input())

def ZZ():
	return [int(_) for _ in input().split()]

class edge:

	def __init__(self, to, cost, t):
		(self.to, self.cost, self.t) = (to, cost, t)

def main():
	(N, M, S) = ZZ()
	(C, D) = ([0] * (N + 1), [0] * (N + 1))
	E = collections.defaultdict(list)
	dist = [[INF] * (MAX_S + 1) for _ in range(N + 1)]
	for _ in range(M):
		(u, v, a, b) = ZZ()
		E[u].append(edge(v, a, b))
		E[v].append(edge(u, a, b))
	for i in range(1, N + 1):
		(C[i], D[i]) = ZZ()
	S = min(S, MAX_S)
	dist[1][S] = 0
	que = list()
	heapq.heapify(que)
	heapq.heappush(que, [dist[1][S], 1, S])
	while que:
		(x, v, s) = heapq.heappop(que)
		if dist[v][s] < x:
			continue
		ns = min(s + C[v], MAX_S)
		if dist[v][ns] > x + D[v]:
			dist[v][ns] = x + D[v]
			heapq.heappush(que, [x + D[v], v, ns])
		for e in E[v]:
			if s - e.cost < 0:
				continue
			if dist[e.to][s - e.cost] > x + e.t:
				dist[e.to][s - e.cost] = x + e.t
				heapq.heappush(que, [x + e.t, e.to, s - e.cost])
	for i in range(2, N + 1):
		output = INF
		for j in range(MAX_S + 1):
			output = min(output, dist[i][j])
		print(output)
	return

def __starting_point():
	main()
__starting_point()