Problem:


Score : 500 points

Problem Statement

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 1

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

Sample Output 1

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.

Sample Input 2

4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4

Sample Output 2

5
5
7

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 4 in 7 minutes, as follows:

At the exchange counter in City 1, exchange 2 gold coins for 6 silver coins in 2 minutes.

Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Use the 4-th railroad to move from City 3 to City 4 in 1 minutes.

Sample Input 3

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1

Sample Output 3

1
9003
14606
16510
16576

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 6 in 16576 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 9000 minutes.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

At the exchange counter in City 3, exchange 8 gold coins for 8 silver coins in 5600 minutes.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

Use the 3-rd railroad to move from City 2 to City 4 in 1 minute.

At the exchange counter in City 4, exchange 19 gold coins for 19 silver coins in 1900 minutes.

Use the 3-rd railroad to move from City 4 to City 2 in 1 minute.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

Use the 4-th railroad to move from City 3 to City 5 in 1 minute.

At the exchange counter in City 5, exchange 63 gold coins for 63 silver coins in 63 minutes.

Use the 4-th railroad to move from City 5 to City 3 in 1 minute.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 5-th railroad to move from City 1 to City 6 in 1 minute.

Sample Input 4

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7

Sample Output 4

1
3
5

The railway network in this input is shown in the figure below:

Sample Input 5

2 1 0
1 2 1 1
1 1000000000
1 1

Sample Output 5

1000000001

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 2 in 1000000001 minutes, as follows:

At the exchange counter in City 1, exchange 1 gold coin for 1 silver coin in 1000000000 minutes.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.



Sample input:
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5


Sample output:
2
14

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
import sys
import bisect
import string
import math
import time

def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

class NeighborList():
    def __init__(self):
        self.neighbor = {}


class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        '''
        dist = {} # 始点から各頂点までの最短距離を格納する
        prev = {} # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        prev[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heappop(q) # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in adj[src].neighbor.keys():
                cost = adj[src].neighbor[dest]#src→destのチェック

                if dest in dist.keys():
                    if dist[dest] > dist[src] + cost:#先のコスト(仮決定) > 今のコスト+移動するのにかかるコスト
                        dist[dest] = dist[src] + cost # distの更新
                        heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                        prev[dest] = src                      # 前の頂点IDを記録
                else:#訪れたことが無ければ
                    dist[dest] = dist[src] + cost # distの更新
                    heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点IDを記録

        if goal is not None:
            return self.get_path(start,goal, prev)
        else:
            return dist

    def get_path(self, start, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != start:
            path.append(prev[dest])
            dest = prev[dest]

        path.append(start)

        # 経路をreverseして出力
        return list(reversed(path))


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

MX = 2500

def trans(e, s):
    return MX * e + s


def main():
    N, M, S = MI()
    U = [0] * M
    V = [0] * M
    A = [0] * M
    B = [0] * M
    C = [0] * N
    D = [0] * N
    edges = [[] for i in range(N)]
    # cost = [[] for i in range(N * MX)]
    adj = {i:NeighborList() for i in range(N * MX)}

    for i in range(M):
        U[i], V[i], A[i], B[i] = MI()
        U[i] -= 1
        V[i] -= 1
        edges[U[i]].append((V[i], i))
        edges[V[i]].append((U[i], i))

    for i in range(N):
        C[i], D[i] = MI()

    for i in range(N):
        for j in range(0, MX):
            to = min(j + C[i], MX-1)
            # cost[trans(i, j)][trans(i, to)] = D[i]
            adj[trans(i, j)].neighbor[trans(i, to)] = D[i]
            for pair in edges[i]:
                to = pair[0]
                idx = pair[1]
                if j - A[idx] >= 0:
                    # cost[trans(i, j)][trans(to, j - A[idx])] = B[idx]
                    adj[trans(i, j)].neighbor[trans(to, j - A[idx])] = B[idx]

    S = min(2499, S)
    # print('S', S)
    d = Dijkstra()
    ret = d.dijkstra(adj, trans(0, S))
    # ret = dijkstra(cost, trans(0, S))

    # print()
    # for i in range(1, N):
    #     print(i, *['IINF' if v == IINF else "{:0=4}".format(v) for v in cost[i]])

    for i in range(1, N):
        ans = IINF
        for j in range(MX):
            # if j <= 4:
            #     print(i, j, cost[i][j])
            ans = min(ans, ret[trans(i, j)])
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys

input = sys.stdin.readline

inf = 10**12

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)]
#visit = [[0]*(P+1) for _ in range(N)]
###heapにぶち込んだことがあるかないか

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:
        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
        heapq.heappush(q,(v[0]+x[0],x[1],v[2]-x[2]))
    
    ###
    #print(P)
    #print(q)
    #print(v)
    ###

for i in range(1,N):
    print(min(dist[i]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

for i in range(n):
    c, d = map(int, input().split())
    cd.append([c, d])

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
SIZE = max_a * n + 1
# SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE+1)] for _ in range(n)]
nodes[0][s] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while 10**6 > len(que) > 0:
        if len(goals) >= n:
            break
        cost, num, silver = heappop(que)
        if num not in goals:
            goals.add(num)
        c, d = cd[num]
        s_tmp = min(SIZE, silver+c)
        if silver < SIZE and s_tmp != silver:
            if nodes[num][s_tmp] > cost + d:
                heappush(que, (cost + d, num, s_tmp))
                nodes[num][s_tmp] = min(nodes[num][s_tmp], cost + d)
        for v in edges[num].keys():
            a, b = edges[num][v]
            if silver >= a:
                if nodes[v][silver-a] > cost + b:
                    heappush(que, (cost + b, v, silver - a))
                    nodes[v][silver - a] = min(nodes[v][silver - a], cost + b)

dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

for i in range(n):
    c, d = map(int, input().split())
    cd.append([c, d])

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
SIZE = max_a * n + 1
# SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE+1)] for _ in range(n)]
nodes[0][s] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        if len(goals) >= n:
            break
        cost, num, silver = heappop(que)
        if num not in goals:
            goals.add(num)
        c, d = cd[num]
        s_tmp = min(SIZE, silver+c)
        if silver < SIZE and s_tmp != silver:
            if nodes[num][s_tmp] > cost + d:
                heappush(que, (cost + d, num, s_tmp))
                nodes[num][s_tmp] = min(nodes[num][s_tmp], cost + d)
        for v in edges[num].keys():
            a, b = edges[num][v]
            if silver >= a:
                if nodes[v][silver-a] > cost + b:
                    heappush(que, (cost + b, v, silver - a))
                    nodes[v][silver - a] = min(nodes[v][silver - a], cost + b)

dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

for i in range(n):
    c, d = map(int, input().split())
    cd.append([c, d])

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
SIZE = max_a * n + 1
# SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE+1)] for _ in range(n)]
nodes[0][s] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        if len(goals) >= n:
            break
        cost, num, silver = heappop(que)
        if num not in goals:
            goals.add(num)
        c, d = cd[num]
        s_tmp = min(SIZE, silver+c)
        if silver < SIZE and s_tmp != silver and nodes[num][s_tmp] > cost + d:
            heappush(que, (cost + d, num, s_tmp))
            nodes[num][s_tmp] = min(nodes[num][s_tmp], cost + d)

        for v in edges[num].keys():
            a, b = edges[num][v]
            if silver >= a and nodes[v][silver-a] > cost + b:
                heappush(que, (cost + b, v, silver - a))
                nodes[v][silver - a] = min(nodes[v][silver - a], cost + b)

dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Wrong Answer

Solution code:
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
    # dijkstra (time, vertex, money)
    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)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        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))
        
        # exchange gold with silver
        rate, time = info[now]
        nt = t + time
        ns = min(s+rate, MAX_SILVER)
        if cost[nv][ns] <= nt : continue
        heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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
    # dijkstra (time, vertex, money)
    exchanged = [False] * N
    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)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        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))
        
        # exchange gold with silver
        if exchanged[now] : continue
        exchanged[now] = True

        rate, time = info[now]
        for i, ns in enumerate(range(s + rate, MAX_SILVER+rate, rate), 1):
            ns = min(ns, MAX_SILVER)
            nt = t + time * i
            if cost[nv][ns] <= nt : continue
            heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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
    # dijkstra (time, vertex, money)
    exchanged = [False] * N
    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)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        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))
        
        # exchange gold with silver
        if exchanged[now] : continue
        exchanged[now] = True

        rate, time = info[now]
        for i, ns in enumerate(range(s + rate, MAX_SILVER+1, rate), 1):
            nt = t + time * i
            if cost[nv][ns] <= nt : continue
            heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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
    # dijkstra (time, vertex, money)
    exchanged = [False] * N
    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)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        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))
        
        # exchange gold with silver
        if exchanged[now] : continue
        exchanged[now] = True
        
        rate, time = info[now]
        for i, ns in enumerate(range(s + rate, MAX_SILVER, rate), 1):
            nt = t + time * i
            if cost[nv][ns] <= nt : continue
            heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def examA():
    S, W = LI()
    if S<=W:
        print("unsafe")
    else:
        print("safe")
    return

def examB():
    A, B, C, D = LI()
    while(True):
        C -= B
        if C<=0:
            print("Yes")
            break
        A -= D
        if A<=0:
            print("No")
            break
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    Set = set(S)
    ans = len(Set)
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    D = [0]*(N+1)
    for i in range(N):
        D[i+1] = (D[i]+int(S[N-1-i])*pow(10,i,2019))%2019
    #print(D)
    ans = 0
    C = Counter(D)
    #print(C)
    for c in C.values():
        ans += (c-1)*c//2
    print(ans)
    return

def examE():
    def dijkstra(n, edges, start, C, silver):
        maxC = (2*n-1)*50
        dist = [[inf]*(maxC+1) for _ in range(n)]
        dist[start][silver] = 0
        Q = [(0, (start, silver))]  # (dist,vertex)
        while (Q):
            d, (v, c) = heapq.heappop(Q)
            if dist[v][c]<d:continue
            loop = (maxC-c)//C[v][0] + 1
            for i in range(loop):
                nextc = c+i*C[v][0]
                nextd = d+i*C[v][1]
                if nextc>maxC:
                    nextc=maxC
                if dist[v][nextc] < nextd: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost, coin in edges[v]:
                    k = nextc-coin
                    if k<0:
                        continue
                    if dist[u][k] > nextd + cost:
                        dist[u][k] = nextd + cost
                        heapq.heappush(Q, (dist[u][nextc-coin], (u, k)))
        return dist
    N, M, S = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t, a, b = LI()
        s -= 1; t -= 1
        V[s].append((t,b,a))
        V[t].append((s,b,a))
    C = [LI()for _ in range(N)]
    D = dijkstra(N,V,0,C,min(S,(2*N-1)*50))
    for i in range(1,N):
        print(min(D[i]))
    return

def examE2():
    def dijkstra(edges, start=0):
        dist = [inf] * len(edges)
        dist[start] = 0
        Q = [(0, start)]  # (dist,vertex)
        while (Q):
            d, v = heapq.heappop(Q)
            if dist[v] < d: continue  # 候補として挙がったd,vだが、他に短いのがある
            for u, cost in edges[v]:
                if dist[u] > dist[v] + cost:
                    dist[u] = dist[v] + cost
                    heapq.heappush(Q, (dist[u], u))
        return dist
    maxS = 2500
    N, M, S = LI()
    V = [[]for _ in range(N*(maxS+1))]

    for _ in range(M):
        u, v, a, b = LI()
        u -= 1; v -= 1
        for i in range(a, maxS):
            V[u * maxS + i].append([v * maxS + i - a, b])
            V[v * maxS + i].append([u * maxS + i - a, b])

    for i in range(N):
        c, d = LI()
        for j in range(maxS):
            V[i * maxS + j].append([i * maxS + min(j + c, maxS), d])
    D = dijkstra(V,min(maxS,S))
    for i in range(1,N):
        print(min(D[i*maxS+1:(i+1)*maxS]))
    return

def examF():
    N = I()
    S = LI()
    T = LI()
    U = LI()
    V = LI()

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
def examA():
    S, W = LI()
    if S<=W:
        print("unsafe")
    else:
        print("safe")
    return

def examB():
    A, B, C, D = LI()
    while(True):
        C -= B
        if C<=0:
            print("Yes")
            break
        A -= D
        if A<=0:
            print("No")
            break
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    Set = set(S)
    ans = len(Set)
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    D = [0]*(N+1)
    for i in range(N):
        D[i+1] = (D[i]+int(S[N-1-i])*pow(10,i,2019))%2019
    #print(D)
    ans = 0
    C = Counter(D)
    #print(C)
    for c in C.values():
        ans += (c-1)*c//2
    print(ans)
    return

def examE():
    def dijkstra(n, edges, start, C, silver):
        maxC = (2*n-1)*50
        dist = [[inf]*(maxC+1) for _ in range(n)]
        dist[start][silver] = 0
        Q = [(0, (start, silver))]  # (dist,vertex)
        while (Q):
            d, (v, c) = heapq.heappop(Q)
            if dist[v][c]<d:continue
            loop = (maxC-c)//C[v][0] + 1
            for i in range(loop):
                nextc = c+i*C[v][0]
                nextd = d+i*C[v][1]
                if nextc>maxC:
                    nextc=maxC
                if dist[v][nextc] < nextd: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost, coin in edges[v]:
                    k = nextc-coin
                    if k<0:
                        continue
                    if dist[u][k] > nextd + cost:
                        dist[u][k] = nextd + cost
                        heapq.heappush(Q, (dist[u][nextc-coin], (u, k)))
        return dist
    N, M, S = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t, a, b = LI()
        s -= 1; t -= 1
        V[s].append((t,b,a))
        V[t].append((s,b,a))
    C = [LI()for _ in range(N)]
    D = dijkstra(N,V,0,C,min(S,(2*N-1)*50))
    for i in range(1,N):
        print(min(D[i]))
    return

def examE2():
    def dijkstra(edges, start=0):
        dist = [inf] * len(edges)
        dist[start] = 0
        Q = [(0, start)]  # (dist,vertex)
        while (Q):
            d, v = heapq.heappop(Q)
            if dist[v] < d: continue  # 候補として挙がったd,vだが、他に短いのがある
            for u, cost in edges[v]:
                if dist[u] > dist[v] + cost:
                    dist[u] = dist[v] + cost
                    heapq.heappush(Q, (dist[u], u))
        return dist
    maxS = 2500
    N, M, S = LI()
    V = [[]for _ in range(N*(maxS+1))]

    for _ in range(M):
        u, v, a, b = LI()
        u -= 1; v -= 1
        for i in range(a, maxS+1):
            V[u * maxS + i].append([v * maxS + i - a, b])
            V[v * maxS + i].append([u * maxS + i - a, b])

    for i in range(N):
        c, d = LI()
        for j in range(maxS):
            V[i * maxS + j].append([i * maxS + min(j + c, maxS), d])
    D = dijkstra(V,min(maxS,S))
    for i in range(1,N):
        print(min(D[i*maxS+1:(i+1)*maxS]))
    return

def examF():
    N = I()
    S = LI()
    T = LI()
    U = LI()
    V = LI()

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""