CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    INF = float('inf')
    N, M = list(map(int, input().split()))
    dist = [0] + [INF] * (N-1)
    abc = []
    
    for i in range(M):
        a, b, c = list(map(int, input().split()))
        abc.append((a, b, -c))
        
    for i in range(N-1):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            dist[b-1] = min(dist[b-1], dist[a-1]+c)
            
    ans = dist[-1]
    negative = [False] * N
    
    for i in range(N):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            elif dist[b-1] > dist[a-1]+c:
                dist[b-1] = dist[a-1]+c
                negative[b-1] = True
            if negative[a-1]:
                negative[b-1] = True
            
    if negative[-1]:
        print('inf')
    else:
        print((-ans))

if __name__ == '__main__':
    main()
    

# Optimized solution
def main():
    INF = float('inf')
    N, M = list(map(int, input().split()))
    dist = [0] + [INF] * (N-1)
    abc = []
    
    for i in range(M):
        a, b, c = list(map(int, input().split()))
        abc.append((a-1, b-1, -c))
            
    for a, b, c in abc:
        dist[b] = min(dist[b], dist[a]+c)
        
    ans = dist[-1]
    
    for a, b, c in abc:
        dist[b] = min(dist[b], dist[a]+c)
            
    if ans != dist[-1]:
        print('inf')
    else:
        print((-ans))

if __name__ == '__main__':
    main()
# Original solution

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

edges = []

for i in range(M):
    a, b, c = list(map(int, input().split()))
    edges.append([a,b,c])

dist = [float('inf')] * (N + 1)
dist[1] = 0

for _ in range(N - 1):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] - c)

ans = dist[N]
for a, b, c in edges:
    dist[b] = min(dist[b], dist[a] - c)

if ans == dist[N]:
    print((-ans))
else:
    print('inf')

# Optimized solution
def main():
    N, M = list(map(int, input().split()))
    edges = []
    
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        edges.append([a,b,c])

    d = [float('inf')] * N
    d[0] = 0

    for i in range(N-1):
        for edge in edges:
            d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

    ans = d[N-1]
    for edge in edges:
        d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

    if ans == d[N-1]:
        print((-ans))
    else:
        print('inf')


main()
# Original solution
n,m = list(map(int , input().split()))

e = []

for i in range(m):
    a,b,c = list(map(int , input().split()))
    e.append((a-1,b-1,c)) 

maxdis = [-float('inf') for i in range(n)]

maxdis[0] = 0
mugen = False

for i in range(2*n):
    for j in e:
        st,gl,cost = j
        if (maxdis[gl] < maxdis[st]+cost):
            maxdis[gl] = maxdis[st]+cost
            if (i >= n-1 and (gl == n-1)): 
                mugen = True 
                break
if mugen:
    print("inf")

else:
    print((maxdis[n-1]))

# Optimized solution
n,m = list(map(int , input().split()))

e = []

for i in range(m):
    a,b,c = list(map(int , input().split()))
    e.append((a-1,b-1,c)) 

maxdis = [-float('inf') for i in range(n)]

maxdis[0] = 0
mugen = False

for i in range(n):
    for j in e:
        st,gl,cost = j
        if (maxdis[gl] < maxdis[st]+cost):
            maxdis[gl] = maxdis[st]+cost
            if (i >= n-1 and (gl == n-1)): 
                mugen = True 
                break
if mugen:
    print("inf")

else:
    print((maxdis[n-1]))
# Original solution
n, m = list(map(int, input().split()))
graph = {}
visited = {}
# 0: not visited, 1: visited
scores = {}
for i in range(n):
    if i == 0:
        scores[i+1] = 0
    else:
        scores[i+1] = float("inf")
    graph[i+1] = {}

for i in range(m):
    a, b, c = list(map(int, input().split()))
    graph[a][b] = -c
    # {1: {2: 4, 3: 5}, 2: {3: 4}}

for i in range(n):
    for v in list(graph.keys()):
        for e in list(graph[v].keys()):
            if scores[e] > scores[v] + graph[v][e]:
                scores[e] = scores[v] + graph[v][e]

ans = -scores[n]
negative = {}
for i in range(n):
    negative[i+1] = False

for i in range(n+1):
    for v in list(graph.keys()):
        for e in list(graph[v].keys()):
            if scores[v] + graph[v][e] < scores[e]:
                scores[e] = scores[v] + graph[v][e]
                negative[e] = True
                if negative[v]:
                    negative[e] = True

if negative[n]:
    print('inf')
else:
    print(ans)

# Optimized solution
n, m = list(map(int, input().split()))
graph = {}
visited = {}
# 0: not visited, 1: visited
scores = {}
for i in range(n):
    if i == 0:
        scores[i+1] = 0
    else:
        scores[i+1] = float("inf")
    graph[i+1] = {}

for i in range(m):
    a, b, c = list(map(int, input().split()))
    graph[a][b] = -c
    # {1: {2: 4, 3: 5}, 2: {3: 4}}

for i in range(n):
    for v in list(graph.keys()):
        for e in list(graph[v].keys()):
            if scores[e] > scores[v] + graph[v][e]:
                scores[e] = scores[v] + graph[v][e]

ans = -scores[n]
negative = {}
for i in range(n):
    negative[i+1] = False

for i in range(n+1):
    if negative[n]:
        break
    for v in list(graph.keys()):
        for e in list(graph[v].keys()):
            if scores[v] + graph[v][e] < scores[e]:
                scores[e] = scores[v] + graph[v][e]
                negative[e] = True
                if negative[v]:
                    negative[e] = True

if negative[n]:
    print('inf')
else:
    print(ans)
# Original solution
import sys
n,m=list(map(int,input().split()))
abc=[list(map(int,input().split())) for i in range(m)]
data=[[] for i in range(n+1)]
for u in abc:
    a,b,c=u
    data[a].append([b,c])
inf=float("inf")
lst=[-inf]*(n+1)
lst[1]=0
que=[1]
count=0
z=0
a,b,c,d=-inf,-inf,-inf,-inf
while que:
    h=[]
    for u in que:
        for v in data[u]:
            w,c=v
            lst[w]=max(lst[w],lst[u]+c)
            h.append(w)
    que=h
    count+=1
    if count==m:
        a=lst[n]
    if count==2*m+5:
        b=lst[n]
        break
    if len(que)>n:
        c=lst[n]
        z=10
    if z>=10:
        z+=1
        if z==15:
            d=lst[n]
            break
else:
    print((lst[n]))
    sys.exit()
if b>a or d>c:
    print("inf")
else:
    print((lst[n]))

# Optimized solution
n,m=list(map(int,input().split()))
abc=[list(map(int,input().split())) for i in range(m)]

inf=float("inf")
data=[-inf]*(n+1)
data[1]=0
for i in range(n):
    for a,b,c in abc:
        if data[a]!=inf:
            data[b]=max(data[b],data[a]+c)

lst=data[:]
for i in range(n):
    for a,b,c in abc:
        if data[a]!=inf:
            data[b]=max(data[b],data[a]+c)

que=[]
for i in range(1,n+1):
    if lst[i]!=data[i]:
        que.append(i)
        
flag=[0]*(n+1)
for u in que:
    flag[u]=1

li=[[] for i in range(n+1)]
for a,b,c in abc:
    li[a].append(b)

while que:
    h=que.pop()
    for u in li[h]:
        if flag[u]==0:
            flag[u]=1
            que.append(u)

if flag[n]==1:
    print("inf")
else:
    print((data[n]))
# Original solution
#負の経路の検出
def find_negative_loop(n, es, d):
    #始点はどこでもよい
    check = [0 for _ in range(n)]
    for _ in range(n):
        for p, q, r in es:
            #e: 辺iについて
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                check[q] = True
            if check[p]:
                check[q] = True
                # if i == n-1:
                #     return True
    return check

def shortest_path(s, n, es):
    #s -> i　の最短経路
    #s: 始点、n: 頂点数、w:辺の数、es[i]: [辺の始点、辺の終点、辺のコスト]
    d = [float("inf")] * n
    #d[i]: s->iの最短距離
    d[s] = 0
    for _ in range(n):
        update = False
        for p, q, r in es:
            #e: 辺iについて
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        # print(update)
        if not update:
            break
    return d

n,w = list(map(int,input().split())) #n:頂点数　w:辺の数
es = [] #es[i]: [辺の始点,辺の終点,辺のコスト]

for _ in range(w):
    x,y,z = list(map(int,input().split()))
    es.append([x-1, y-1, -z])
    # es.append([y,x,z])

# print(shortest_path(0, n, es))
# print(es)

# if find_negative_loop(n,es):

d = shortest_path(0, n, es)

# print(d)

c = find_negative_loop(n, es, d)
# print(c)



if c[-1]:
    print("inf")
else:
    # d = shortest_path(0, n, es)
    print((-d[-1]))

# Optimized solution
n, m = list(map(int, input().split()))
edge = []

for _ in range(m):
    a, b, c = list(map(int, input().split()))
    edge.append([a-1, b-1, -c])

d = [float("inf") for _ in range(n)]
d[0] = 0

check = [0 for _ in range(n)]

for i in range(n):
    for now, next, weight in edge:
        if d[next] > d[now] + weight:
            d[next] = d[now] + weight
            if i == n-1:
                check[next] = 1
        if i == n-1:
            if check[now]:
                check[next] = 1

if check[-1]:
    print("inf")
else:
    print((-d[-1]))
# Original solution
def bellman_ford(V, E, s, std):
  dist = [float('inf') for _ in range(V)]
  dist[s] = 0
  for i in range(V):
    for s, t, d in std:
      s -=1
      t -= 1
      d = -d
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d 
        if i == V-1 and t+1 == V:
          return -1 
  return dist

def main():
  N, M = list(map(int, input().split()))
  abc = [list(map(int, input().split())) for _ in range(M)]
  dist = bellman_ford(N, M, 0, abc)
  if dist == -1:
    print('inf')
    exit()
  else:
    print((-dist[N-1]))

if __name__ == "__main__":
  main()

# Optimized solution

n, m = list(map(int, input().split()))
abc = []
for _ in range(m):
  a, b, c = list(map(int, input().split()))
  a -= 1
  b -= 1
  c *= -1
  abc += [[a,b,c]]

def bellman_ford(s):
  # std = [[s0, t0, d0], [s1, t1, d1], ... , [sm, tm, dm]]
  # (si, ti, di): si, ti間に重さdiの辺がある
  dist = [float('inf')]*n 
  dist[s] = 0
  for u in range(n):
    for s, t, d in abc:
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d
        if u == n-1 and t == n-1:
          return -1
  return dist

dist = bellman_ford(0)
if dist == -1:
  print('inf')
else:
  print((-1*dist[n-1]))
# Original solution

n, m = list(map(int, input().split()))
abc = []
for _ in range(m):
  a, b, c = list(map(int, input().split()))
  a -= 1
  b -= 1
  c *= -1
  abc += [[a,b,c]]

def bellman_ford(s):
  # std = [[s0, t0, d0], [s1, t1, d1], ... , [sm, tm, dm]]
  # (si, ti, di): si, ti間に重さdiの辺がある
  dist = [float('inf')]*n 
  dist[s] = 0
  for u in range(n):
    for s, t, d in abc:
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d
        if u == n-1 and t == n-1:
          return -1
  return dist

dist = bellman_ford(0)
if dist == -1:
  print('inf')
else:
  print((-1*dist[n-1]))



# Optimized solution
n, m = list(map(int, input().split()))
std = []
for _ in range(m):
  a, b, c = list(map(int, input().split()))
  a -= 1
  b -= 1
  std += [[a, b, -c]]

def bellman_ford(s):
  # std = [[s0, t0, d0], [s1, t1, d1], ... , [sm, tm, dm]]
  # (si, ti, di): si, ti間に重さdiの辺がある
  dist = [float('inf')]*n 
  dist[s] = 0
  for u in range(n):
    for s, t, d in std:
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d
        if u == n-1 and t == n-1:
          return -1
  return dist

dist = bellman_ford(0)
if dist != -1:
  print((-dist[n-1]))
else:
  print('inf')
# Original solution
import sys
N, M = list(map(int, input().split()))
edge = [list(map(int, input().split())) for _ in range(M)]

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(N):
    for n, nn, c in edge:
        if cost[nn] < cost[n] + c:
            # ワーシャルフロイド法の性質より、N回目に更新があるならinf
            if i == N - 1 and nn == N:
                print("inf")
                sys.exit()
            cost[nn] = cost[n] + c

print((cost[N]))

# Optimized solution
# ABC061 D - Score Attack
import sys
N, M = list(map(int, input().split()))
edge = [list(map(int, input().split())) for _ in range(M)]

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(N):
    for n, nn, c in edge:
        if cost[nn] < cost[n] + c:
            # ベルマンフォード法の性質より、N回目に更新があるならinf
            if i == N - 1 and nn == N:
                print("inf")
                sys.exit()
            cost[nn] = cost[n] + c

print((cost[N]))
# Original solution
# coding: utf-8
# Your code here!

def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    negative = [False]*n
    for i in range((2*n)):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if negative[v]: negative[to] = True
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
                if i >= n:
                    negative[to] = True
        if not updated: break
    if negative[-1]: return None, False
    return dist, True


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c))
#    g[b-1].append((a-1,c))

dist, TF = Bellman_Ford(g, 0)

if TF: print((-dist[-1]))
else: print("inf")




# Optimized solution
# coding: utf-8
# Your code here!

def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    
    for i in range(n<<1):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
        if not updated: break
        if i <= n: a0 = dist[-1]
    if a0 != dist[-1]: return None, False
    return dist, True


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c))
#    g[b-1].append((a-1,c))

dist, TF = Bellman_Ford(g, 0)

if TF: print((-dist[-1]))
else: print("inf")
# Original solution
n, m = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(m)]


def bellman_ford(s, g):
	dist = [float("inf")] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[a] == float("inf"):
				continue

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True

	if negative[g]:
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)


# Optimized solution
n, m = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(m)]


def bellman_ford(s, g):
	dist = [float("inf")] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True

	if negative[g]:
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)
# Original solution
# coding: utf-8
n,m=list(map(int,input().split()))
edge=[]
for i in range(m):
    a,b,c=list(map(int,input().split()))
    edge.append((a-1,b-1,-c))
inf=99999999999999999999
d=[inf for i in range(n)]
d[0]=0
count=0
while True:
    count+=1
    if count==n:
        tmp=d[n-1]
    update=False
    for i in range(m):
        f,t,cost=edge[i]
        if(d[t]>d[f]+cost):
            d[t]=d[f]+cost
            update=True
    if count==n and tmp!=d[n-1]:
        print('inf')
        break
    if not update:
        print((-d[n-1]))
        break
else:
    print((-d[n-1]))

# Optimized solution
# coding: utf-8
n,m=list(map(int,input().split()))
edge=[]
for i in range(m):
    a,b,c=list(map(int,input().split()))
    edge.append((a-1,b-1,-c))
inf=99999999999999999999
d=[inf for i in range(n)]
d[0]=0
count=0
while count<n+1:
    count+=1
    if count==n:
        tmp=d[n-1]
    update=False
    for i in range(m):
        f,t,cost=edge[i]
        if(d[t]>d[f]+cost):
            d[t]=d[f]+cost
            update=True
    if count==n and tmp!=d[n-1]:
        print('inf')
        break
    if not update:
        print((-d[n-1]))
        break
else:
    print((-d[n-1]))
# Original solution

MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = list(map(int, input().split()))
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


# Optimized solution

MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = list(map(int, input().split()))
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
# Original solution
inf = float('inf')

N, M = list(map(int,input().split()))
edges = []
for _ in range(M):
    a, b, c = list(map(int,input().split()))
    a -= 1; b-= 1
    edges.append((a, b, -c))

dist = [inf] * N
dist[0] = 0
for _ in range(N-1):
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            dist[nv] = dist[v] + w

is_update = [False] * N
for _ in range(N):
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            dist[nv] = dist[v] + w
            is_update[nv] = True
        if is_update[v] is True:
            is_update[nv] = True

if is_update[N-1] is True:
    ans = "inf"
else:
    ans = -dist[N-1]

print(ans)

# Optimized solution
inf = float('inf')
# ベルマンフォード法
# 計算量O(VE) V:頂点数, E:辺の数
# [引数]   n:頂点数, edges:辺集合, start:始点, end:終点
# [返り値] dist:startからの最短距離, exists_negative_cycle: 負閉路が存在するかどうか
def bellmanford(n : int, edges : list, start : int, goal : int) -> (list, bool):
    dist = [inf] * n
    dist[start] = 0
    exist_negative_cycle = True

    # 負閉路を含まないとき、頂点数nなら更新は高々n-1回で済む
    for _ in range(N-1):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w


    # (1)グラフに負閉路が含まれるときの検出
    # N回目で更新があったとき、グラフは負閉路を含む
    # for v, nv, w in edges:
    #     if dist[nv] > dist[v] + w:
    #         is_cycle = False

    # (2)startとendのパスに負閉路が含まれるときの検出
    is_updated = [False] * n
    for _ in range(N):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                is_updated[nv] = True
            if is_updated[v] is True:
                is_updated[nv] = True

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

N, M = list(map(int,input().split()))
edges = []
for _ in range(M):
    a, b, c = list(map(int,input().split()))
    a -= 1; b -= 1
    edges.append((a, b, -c))

dist, exist_negative_cycle = bellmanford(N, edges, 0, N-1)

if exist_negative_cycle is True:
    ans = "inf"
else:
    ans = -dist[N-1]

print(ans)
# Original solution
class SegmentTree:

    def __init__(self, n, sentinel=0):
        n2 = 1 << (n - 1).bit_length()
        self.n = n2
        self.data = [sentinel] * ((n2 << 1) - 1)
        self.offset = n2 - 1

    def update(self, k, x):
        i = k + self.offset
        self.data[i] = x
        while i:
            p = (i - 1) // 2
            if self.data[p] > self.data[i]:
                self.data[p] = self.data[i]
            else:
                break
            i = p

    def get_left_min(self, k):
        i = k + self.offset - 1
        ret = self.data[i]
        while i:
            if i % 2 == 0:
                ret = min(ret, self.data[i - 1])
            i = (i - 1) // 2
        return ret

    def get_right_min(self, k):
        i = k + self.offset + 1
        ret = self.data[i]
        while i:
            if i % 2 == 1:
                ret = min(ret, self.data[i + 1])
            i = (i - 1) // 2
        return ret


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

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

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n, d = list(map(int, input().split()))
aaa = list(map(int, input().split()))
seg_l = SegmentTree(n, (10 ** 10, -1))
seg_r = SegmentTree(n, (10 ** 10, -1))
bbb = sorted((a, i) for i, a in enumerate(aaa))
edges = set()

for a, i in bbb:
    cost_l = -i * d + a
    cost_r = i * d + a
    seg_l.update(i, (cost_l, i))
    seg_r.update(i, (cost_r, i))

    di = i * d
    if i > 0:
        base_cost, j = seg_l.get_left_min(i)
        if j > -1:
            edges.add((base_cost + di + a, j, i))
    if i < n - 1:
        base_cost, j = seg_r.get_right_min(i)
        if j > -1:
            edges.add((base_cost - di + a, i, j))

uft = UnionFind(n)
ans = 0
for c, i, j in sorted(edges):
    if uft.find(i, j):
        continue
    ans += c
    uft.union(i, j)

print(ans)


# Optimized solution
from itertools import accumulate
from operator import itemgetter

n, d = list(map(int, input().split()))
aaa = list(map(int, input().split()))
costs_l = [(-i * d + a, i) for i, a in enumerate(aaa)]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]

costs_l = list(accumulate(costs_l, min))
costs_r = list(accumulate(reversed(costs_r), min))
costs_r.reverse()

hubs = set(map(itemgetter(1), costs_l))
hubs.intersection_update(list(map(itemgetter(1), costs_r)))
hubs.add(0)
hubs.add(n - 1)
hubs = sorted(hubs)

ans = sum(aaa) - aaa[-1]
s = hubs[0]
for t in hubs[1:]:
    cls = costs_l[s][0]
    crt = costs_r[t][0]
    ans += crt - s * d
    ans += sum(min(cls + i * d, crt - i * d) for i in range(s + 1, t))
    s = t
print(ans)