def NVP INF 10 10 map int input split if n-1 INF for in range for in r

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def NVP():
INF = 10**10
n, m, k, s, f = map(int,input().split())
if k>=n:k=n-1
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 j in range(1, n):
for i in range(n):
d[j][i] = d[j - 1][i]
for s in range(n):
if d[j - 1][s] + g[s][i] < d[j][i] and g[s][i] != INF:
d[j][i] = d[j - 1][s] + g[s][i]
if d[k][f] == INF: print(-1)
else: print(d[k][f])
NVP()