Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
inf = float('inf')
d = [[inf for j in range(N)] for i in range(N)]

for i in range(N):
    d[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    t = min(c, d[a][b])
    if d[a][b] > c:
        d[a][b], d[b][a] = t, t

for i in range(N):
    for j in range(N):
        for k in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = inf
for i in list(itertools.permutations(r)):
    temp = 0
    for j in range(len(i)-1):
        temp += d[i[j]-1][i[j+1]-1]
        if temp > ans:
            break
    ans = min(ans, temp)

print(ans)

### FIXED CODE ###

from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i in range(N)]

    for i in range(N):
        d[i][i] = 0

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if d[a][b] > c:
            d[a][b], d[b][a] = c, c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp

    print(ans)


main()
### BUGGY CODE ###

mod = 10**9+7
s = input()[::-1]
dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]
dp[0][0] = 1
ten = 1
for i in range(len(s)):
    if s[i]=="?":
        for j in range(10):
            q = (ten*j)%13
            for jj in range(13):
                dp[i+1][(jj+q)%13] = (dp[i][jj]+dp[i+1][(jj+q)%13])%mod
    else:
        q = (ten*int(s[i]))%13
        for jj in range(13):
            dp[i+1][(jj+q)%13] = (dp[i][jj]+dp[i+1][(jj+q)%13])%mod
    ten = (ten*10)%13
print(dp[-1][5])

### FIXED CODE ###

mod = 10**9+7
s = input()[::-1]
dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]
dp[0][0] = 1
ten = 1
for i in range(len(s)):
    if s[i]=="?":
        for j in range(10):
            q = (ten*j)%13
            for jj in range(13):
                dp[i+1][(jj+q)%13] = (dp[i][jj]+dp[i+1][(jj+q)%13])%mod
    else:
        q = (ten*int(s[i]))%13
        for jj in range(13):
            dp[i+1][(jj+q)%13] = (dp[i][jj]+dp[i+1][(jj+q)%13])%mod
    ten = (ten*10)%13
print(dp[-1][5])
### BUGGY CODE ###

N = int(input())
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))

cnt = 0
AB.reverse()
for el in AB:
    A, B = el
    A += cnt
    while A % B != 0:
        A += 1
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))

cnt = 0
AB.reverse()
for el in AB:
    A, B = el
    A += cnt
    if A % B != 0:
        cnt += (B - A % B)
print(cnt)
### BUGGY CODE ###

a, b, c, k = list(map(int, input().split()))

nums = []
for _ in range(a):
  nums.append(1)
for _ in range(b):
  nums.append(0)
for _ in range(c):
  nums.append(-1)

print(sum(nums[:k]))

### FIXED CODE ###

a, b, c, k = list(map(int, input().split()))

max = 0
if(a >= k):
  max = k
else:
  max = a
  k -= a
  if(b >= k):
    pass
  else:
    k -= b
    max -= k

print(max)
### BUGGY CODE ###

nm = lambda : map(int,input().split())
nl = lambda : list(nm())

import bisect

n = int(input())
l = nl()
l.sort()
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        a,b = l[i],l[j]
        if a > b:
            a,b = b,a
        lef = bisect.bisect_right(l,b-a)
        rig = bisect.bisect_left(l,a+b)
        t = rig - lef - 1 - (b < 2*a)
        ans += t
print(ans//3)

### FIXED CODE ###

nm = lambda : map(int,input().split())
nl = lambda : list(nm())

import bisect

n = int(input())
l = nl()
l.sort()
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        a,b = l[i],l[j]
        if a > b:
            a,b = b,a
        lef = bisect.bisect_right(l,b-a)
        rig = bisect.bisect_left(l,a+b)
        t = rig - lef - 1 - (b < 2*a)
        ans += t
print(ans//3)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
n=int(input())
li=[]
f=[len(make_divisors(i)) for i in range(1,n+1)]
for i in range(1,n+1):
    li.append(i*f[i-1])
print(sum(li))

### FIXED CODE ###

n=int(input())

#L=[n//i*(i+n//i*i)//2 for i in range(1,n+1)]
#print(sum(L))
ans=0
#for i in range(1,n+1):
#    for j in range(1,n+1):
#        if i%j==0:
#            ans+=i
#print(ans)
g=lambda x:(x*(n//x)*(n//x+1))//2
print(sum(g(i) for i in range(1,n+1)))
### BUGGY CODE ###

#s<t!
#一番期待値が悪くなる辺だけ考える
n,m = map(int, input().split( ))

E= [[] for _ in range(n)]

for _ in range(m):
    s,t = map(int, input().split( ))
    E[s-1].append(t-1)

dp = [0]*n 

for s in range(n-2,-1,-1):
    for t in E[s]:
        dp[s] += dp[t]
    if E[s]:
        dp[s] /= len(E[s])
    dp[s] += 1

#print("dp",*dp)

ans = dp[0]
for s2 in range(n-1):
    if len(E[s2])-1:
        dp2 = [0]*n
        for s in range(n-2,-1,-1):
            mxi = 0
            for t in E[s]:
                dp2[s] += dp2[t]
                if s ==s2:
                    mxi = max(mxi,dp[t])
            dp2[s] -= mxi
            if s == s2:
                dp2[s] /= len(E[s])-1
            elif E[s]:##el if
                dp2[s] /= len(E[s])
            dp2[s] += 1
        ans = min(ans, dp2[0])
        #print("dp2",*dp2)

print(ans)

### FIXED CODE ###

#s<t!
#一番期待値が悪くなる辺だけ考える
n,m = map(int, input().split( ))

E= [[] for _ in range(n)]

for _ in range(m):
    s,t = map(int, input().split( ))
    E[s-1].append(t-1)

dp = [0]*n 

for s in range(n-2,-1,-1):
    for t in E[s]:
        dp[s] += dp[t]
    if E[s]:
        dp[s] /= len(E[s])
    dp[s] += 1

#print("dp",*dp)

ans = dp[0]
for s2 in range(n-1):
    if len(E[s2])-1:
        dp2 = [0]*n
        mxi = 0
        mxt = -1
        for t in E[s2]:
            if mxt<dp[t]:
                mxi = t 
                mxt = dp[t]
        if mxt<0:
            continue            
        for s in range(n-2,-1,-1):
            for t in E[s]:
                dp2[s] += dp2[t]
            if s ==s2:###ループ深さ
                dp2[s] -= mxt
            if s == s2:
                dp2[s] /= (len(E[s])-1)
            elif E[s]:##el if
                dp2[s] /= len(E[s])
            dp2[s] += 1
        ans = min(ans, dp2[0])
        #print("dp2",*dp2)

print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N, M =map(int, input().split())
G=[[]for i in range(N+1)]
for i in range(M):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,-c),

d = [10**9]*(N+1)
flag = True
def f(v, u):
    global flag
    if not flag:
        d[v] = 0
        return 0
    else:
        d[v] = u
        for t, c in G[v] :
            if d[t] == 10**9:
                f(t, u+c)
            else:
                if d[t] != u+c:
                    flag = False
                    
for i in range(1, N+1):
    if d[i] == 10**9:
        f(i, 0)
    else:
        f(i, d[i])
if flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N, M =map(int, input().split())
G=[[]for i in range(N+1)]
for i in range(M):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,-c),

d = [10**9]*(N+1)
flag = True
def f(v, u):
    global flag
    if not flag:
        d[v] = 0
        return 0
    else:
        d[v] = u
        for t, c in G[v] :
            if d[t] == 10**9:
                f(t, u+c)
            else:
                if d[t] != u+c:
                    flag = False
                    
for i in range(1, N+1):
    if d[i] == 10**9:
        f(i, 0)
if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N = int(input())
total = 0
while N != 0:
  total += N % 10
  N //= 10
#print(total)
if total % 9 == 0 or total == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
total = list(str(N))
ntotal = 0
for i in range(len(total)):
  ntotal += int(total[i])
#print(ntotal,ntotal % 9)
if ntotal % 9 == 0 or ntotal == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        up = (i+j+1)*80+1
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()

### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            up = min((i+j+1)*80+1, ma-k)
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()
### BUGGY CODE ###

n=int(input())
s={}
for i in range(n):
    st=input()
    if st in s:
        s[st]+=1
    else:
        s[st]=1
ans=[kv[0] for kv in s.items() if kv[1] == max(s.values())]
ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

n=int(input())
s={}
ans=[]
max=0
for i in range(n):
    st=input()
    if st in s:
        s[st]+=1
    else:
        s[st]=1
    if max<s[st]:
        max=s[st]
        ans=[st]
    elif max==s[st]:
        ans.append(st)
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

n, m = map(int, input().split())
lrl = list(list(map(int, input().split())) for _ in range(m))
idl = [0]*n
count = 0

for lr in lrl:
    for i in range(lr[0]-1, lr[1]):
        idl[i] += 1

for i in idl:
    if i == m:
        count += 1

print(count)



### FIXED CODE ###

n, m = map(int, input().split())
lrl = list(list(map(int, input().split())) for _ in range(m))
lmax = 0
rmin = n

for lr in lrl:
    if lr[0] > lmax:
        lmax = lr[0]
    if lr[1] < rmin:
        rmin = lr[1]
if lmax <= rmin:
    print(rmin-lmax+1)
else:
    print(0)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.parent = [ -1 for _ in range(n) ]
        self._size = n

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.root(self.parent[x])

    def size(self, x):
        return -self.parent[self.root(x)]


N, M, K = map(int, input().split())

uf_tree1 = UnionFind(N)
uf_tree2 = UnionFind(N)

friends = [ [] for _ in range(N) ]
blocks = [ [] for _ in range(N) ]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    uf_tree1.unite(a, b)
    friends[a].append(b)
    friends[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    c -= 1; d -= 1;
    uf_tree2.unite(c, d)
    blocks[c].append(d)
    blocks[d].append(c)

for i in range(N):
    ans = uf_tree1.size(i) - 1
    cand = set()
    for f in friends[i]:
        cand.add(f)
    for b in blocks[i]:
        if uf_tree1.same(i, b):
            cand.add(b)
    ans -= len(cand)
    print(ans, end = "")
    print("\n" if i == N-1 else " ", end = "")

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.parent = [ -1 for _ in range(n) ]
        self._size = n
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def size(self, x):
        return -self.parent[self.root(x)]

n, m, k = map(int, input().split())
friends = [ [] for _ in range(n) ]
blocks  = [ [] for _ in range(n) ]

tree = UnionFind(n)

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    friends[a].append(b)
    friends[b].append(a)
    tree.unite(a, b)

for _ in range(k):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    blocks[a].append(b)
    blocks[b].append(a)

for i in range(n):
    ret = tree.size(i)
    s = set()
    for j in friends[i]:
        s.add(j)
    for j in blocks[i]:
        if tree.same(i, j):
            s.add(j)
    ret -= len(s)
    print(ret-1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ua=list(set(a))
total=sum([sum(range(a.count(x))) for x in ua])
d={}
total=0
for x in ua:
    c=a.count(x)
    d[x]=c
    total+=sum(range(c))
for x in a:
    print(total-d[x]+1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
d={}
for x in a:
    if d.get(x) is None:
        d[x]=1
        continue
    d[x]+=1
total=0
for v in d.values():
    total+=(v-1)*v//2
for x in a:
    print(total-d[x]+1)
### BUGGY CODE ###

ans_set=set()
N=int(input())
s=input()

for i in range(0,N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            ans_set.add(s[i]+s[j]+s[k])

print(len(ans_set))


### FIXED CODE ###

N=int(input())
s=input()

count=0

for i in range(0,10):
    if str(i) in s[:-2]:
        index_1=s.index(str(i))

        for j in range(0,10):
            if str(j) in s[index_1+1:-1]:
                index_2=s[index_1+1:-1].index(str(j))+index_1+1

                for k in range(0,10):
                    if str(k) in s[index_2+1:]:
                        count+=1
print(count)
### BUGGY CODE ###

N = int(input())
G = [[int(x) for x in input()] for k in range(N)]
es = [[] for k in range(N)]

for k in range(N):
    for l in range(N):
        if G[k][l] == 1:
            es[k].append(l)

#
# 二部グラフ判定by prdさん
#

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

if is_bipartite() == False:
    print(-1)
    exit(0)

# ワーシャルフロイドで距離を求める
D = [[1000 for k in range(N)] for l in range(N)]
for k in range(N):
    for l in range(N):
        if k == l:
            D[k][l] = 0
        elif G[k][l] == 1:
            D[k][l] = 1

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[p][q] = min(D[p][q],D[p][r]+D[r][q])
ans = 0
for k in range(N):
    for l in range(N):
        ans = max(ans, D[k][l]+1)

print(ans)


### FIXED CODE ###

N = int(input())
G = [[int(x) for x in input()] for k in range(N)]
es = [[] for k in range(N)]

for k in range(N):
    for l in range(N):
        if G[k][l] == 1:
            es[k].append(l)

#
# 二部グラフ判定by prdさん
#

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

if is_bipartite() == False:
    print(-1)
    exit(0)

# ワーシャルフロイドで距離を求める
D = [[float("inf") for k in range(N)] for l in range(N)]
for k in range(N):
    for l in range(N):
        if k == l:
            D[k][l] = 0
        elif G[k][l] == 1:
            D[k][l] = 1

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r],D[q][p]+D[p][r])
ans = 0
for k in range(N):
    for l in range(N):
        ans = max(ans, D[k][l]+1)

print(ans)
### BUGGY CODE ###

from bisect import bisect_left,bisect_right

n=int(input())
l=sorted(list(map(int,input().split())))
cnt=0
for i in range(n):
    for j in range(i+1,n):
        MIN=abs(l[i]-l[j])
        MAX=l[i]+l[j]
        min_idx=bisect_right(l,MIN)
        max_idx=bisect_left(l,MAX)
        min_idx=max(min_idx,j+1)
        res=max_idx-min_idx
        if res<0:continue
        if min_idx<=i<=max_idx:res-=1
        if min_idx<=j<=max_idx:res-=1
        cnt+=(max(res,0))
print(cnt)

### FIXED CODE ###

from bisect import bisect_left,bisect_right

n=int(input())
l=sorted(list(map(int,input().split())))
cnt=0
for i in range(n):
    lim=False
    for j in range(i+1,n):
        MIN=abs(l[i]-l[j])
        MAX=l[i]+l[j]
        min_idx=max(bisect_right(l,MIN),j+1)
        if not lim:
            max_idx=bisect_left(l,MAX)
            if max_idx==n:lim=True
        res=max_idx-min_idx
        if min_idx<=i<=max_idx:res-=1
        if min_idx<=j<=max_idx:res-=1
        cnt+=max(res,0)
print(cnt)
### BUGGY CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
tmp = {}
for i in range(n):
    a_copy = a[:]
    a_copy.remove(a[i])
    k = a[i]
    if k in tmp:
        print(tmp[k])
    else:
        c = collections.Counter(a_copy)
        cnt = 0
        for i in c.values():
            cnt += i * (i-1) // 2
    
        tmp[k] = cnt
    
        print(cnt)

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
cnt = 0
c = collections.Counter(a)
for i in c.values():
    cnt += i*(i-1) // 2
for j in range(n):
    print(cnt - c[a[j]] + 1)
### BUGGY CODE ###

from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()

lcm = int(N * M / gcd(N, M))
nn = lcm // N
mm = lcm // M
flg = True

for i in range(lcm):
    if i % nn == 0 and i % mm == 0:
        if S[i//nn] == T[i//mm]:
            continue
        else:
            flg = False
if flg:
    print(lcm)
else:
    print(-1)


### FIXED CODE ###

from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()

GCD = gcd(N, M)
LCM = int(N * M / GCD)
flg = True

for i in range(GCD):
    if S[i*N//GCD] == T[i*M//GCD]:
        continue
    else:
        flg = False
if flg:
    print(LCM)
else:
    print(-1)
### BUGGY CODE ###

n,m,p = map(int, input().split())
edge = []
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
if not t:
  print(max(0,-dis[n]))
else:
  redu = [0]*(n+1)
  for v in t:
    redu[v] = 1
  for i in range(n-1):
    for a,b,c in edge:
      if dis[b] > dis[a] + c:
        dis[b] = dis[a] + c
        redu[b] |= redu[a]
    if redu[n]:
      print(-1)
      break
  else:
    print(max(0,-dis[n]))


### FIXED CODE ###

n,m,p = map(int, input().split())
edge = []
e1 = [list() for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
  e1[a].append(b)
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
s = set(t)
while t:
  v = t.pop()
  for x in e1[v]:
    if x == n:
      print(-1)
      exit(0)
    if x in s:
      continue
    s.add(x)
    t.append(x)
print(max(0,-dis[n]))
### BUGGY CODE ###

def main():
    K, S = map(int, raw_input().split())

    count = 0

    # X
    for i in range(K+1):
        # Y
        for j in range(K+1):
            # Z
            for k in range(K+1)[::-1]:
                if i + j + k == S:
                    count += 1
                if i + j + k < S:
                    break

    print count

main()

### FIXED CODE ###

def main():
    K, S = map(int, raw_input().split())

    count = 0

    # X
    for i in range(K+1):
        # Y
        for j in range(K+1):
            if i + j > S:
                break
            if S-i-j > K:
                continue
            count += 1

    print count

main()
### BUGGY CODE ###

_N, _M = [int(_) for _ in input().split()]


def calc(N, M):
    ans = 0
    for i in range(M):
        tmp = 1
        if M > i + 1:
            tmp += 1
        if N > 1:
            tmp += 1
        if N > 1 and M > i + 1:
            tmp += 1
        if N > 1 and i - 1 >= 0:
            tmp += 1
        if i > 0:
            tmp += 1

        ans += tmp % 2
        # print(tmp, ans)
    if N >= 2:
        ans = ans * 2
    return ans


res = calc(_N, _M)

if _N >= 3:
    res += calc(_M, _N - 2)

if _N >= 3 and _M >= 3:
    res += (_N - 2) * (_M - 2)
print(res)

### FIXED CODE ###

_N, _M = [int(_) for _ in input().split()]


def calc(N, M):
    ans = 0

    def hashicco(n, m):
        tmp = 1
        if n > 1:
            tmp += 1
        if m > 1:
            tmp += 1
            if n > 1:
                tmp += 1
        res = tmp % 2
        if n > 1:
            res *= 2
        if n > 1:
            res *= 2
        return res

    # ans += hashicco(N, M)

    v = 0
    if M > 2 and N == 1:
        v += M - 2
    h = 0
    if N > 2 and M == 1:
        h += N - 2

    return hashicco(N,M)+v+h


res = calc(_N, _M)

if _N >= 3 and _M >= 3:
    res += (_N - 2) * (_M - 2)
print(res)
### BUGGY CODE ###

from bisect import bisect_right, bisect_left

n = int(input())

a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))

ans = 0

for x in b:
  i = bisect_left(a, x)
  j = bisect_right(c, x)

  ans += len(a[:i]) * len(c[j:])

print(ans)

### FIXED CODE ###

from bisect import bisect_right, bisect_left

n = int(input())

a = sorted(list(map(int, input().split())))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())))

ans = 0
for x in b:
  ans += bisect_left(a, x) * (n - bisect_right(c, x))

print(ans)