map int input split if INF 10 10 INF for in range for in range map int

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
n, m ,k ,s ,f = map(int, input().split())
if k >= n: k = n - 1
INF = 10**10
g = [[INF]*n for i in range(n)]
s -= 1; f -= 1
for i in range(m):
u, v, w = map(int, input().split())
g[u - 1][v - 1] = min(w , g[u - 1][v - 1])
d = [[INF] * n for i in range(n)]
d[0][s] = 0
for k2 in range(1, n):
for i in range(n):
d[k2][i] = d[k2 - 1][i]
for j in range(n):
if d[k2 - 1][j] + g[j][i] < d[k2][i] and g[j][i] != INF:
d[k2][i] = d[k2 - 1][j] + g[j][i]
if d[k][f] == INF: print(-1)
else: print(d[k][f])