参考になったダイクストラ法
from heapq import heappush, heappop
import math
INF = 10 ** 18
def dijkstra(s, n): # (始点, ノード数)
dist = [INF] * n
hq = [(0, s)] # (distance, node)
dist[s] = 0
seen = [False] * n # ノードが確定済みかどうか
while hq:
v = heappop(hq)[1] # ノードを pop する
if seen[v]:
continue
seen[v] = True
for to, cost, k in adj[v]: # ノード v に隣接しているノードに対して
if seen[to] == False and math.ceil(dist[v]/k)*k + cost < dist[to]:
dist[to] = cost + math.ceil(dist[v]/k)*k
heappush(hq, (dist[to], to))
return dist
N,M,X,Y=map(int,input().split())
adj = [[] for _ in range(N)]
for i in range(M):
a, b, t, k = map(int, input().split())
adj[a-1].append*1
adj[b-1].append*2
L=dijkstra(X-1,N)
if L[Y-1]==INF:
print(-1)
else:
print(L[Y-1])
