Problem:


Score : 400 points

Problem Statement

There is a directed graph with N vertices and M edges.
The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i.
We will play the following single-player game using this graph and a piece.

Initially, the piece is placed at vertex 1, and the score of the player is set to 0.
The player can move the piece as follows:

When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.

The player can end the game only when the piece is placed at vertex N.
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.

When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.

Constraints

2≤N≤1000 

1≤M≤min(N(N-1),2000) 

1≤a_i,b_i≤N (1≤i≤M) 

a_i≠b_i (1≤i≤M) 

a_i≠a_j or b_i≠b_j (1≤i<j≤M) 

-10^9≤c_i≤10^9 (1≤i≤M)

c_i is an integer.

In the given graph, there exists a path from vertex 1 to vertex N.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.  

Sample Input 1

3 3
1 2 4
2 3 3
1 3 5

Sample Output 1

7

There are two ways to move the piece to vertex N=3:

vertex 1 → vertex 2 → vertex 3 : score 4+3=7

vertex 1 → vertex 3 : score 5

Thus, the maximum possible score at the end of the game is 7.

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

inf

It is possible to increase the score indefinitely by alternating between vertex 1 and 2.

Sample Input 3

6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000

Sample Output 3

-5000000000



Sample input:
3 3
1 2 4
2 3 3
1 3 5


Sample output:
7

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])
ac=[]
flag=[0 for i in range(N+1)]
for i in range(1,N+1):
    stack=[[i,0]]
    visited=set([i])
    while stack:
        p,m=stack.pop()
        for np,value in data[p]:
            if not np in visited:
                visited.add(np)
                stack.append([np,m+value])
            else:
                if m+value>0:
                    flag[i]=1
        if flag[i]:
            break
flaglst=set([i for i in range(len(flag)) if flag[i]==1])
stack=[[1,0,set([1]),1 in flaglst]]
while stack:
    p,m,visited,flag=stack.pop()
    for np,value in data[p]:
        if not flag and np in flaglst:
            flag=1
        if np==N:
            if flag:
                print("inf")
                exit()
            else:
                ac.append(m+value)
        if not np in visited:
            tempvisited=copy.copy(visited)
            tempvisited.add(np)
            stack.append([np,m+value,tempvisited,flag])
print(max(ac))

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])
ac=[]
flag=[0 for i in range(N+1)]
for i in range(1,N+1):
    stack=[[i,0]]
    visited=set([i])
    while stack:
        p,m=stack.pop()
        for np,value in data[p]:
            if not np in visited:
                visited.add(np)
                stack.append([np,m+value])
            else:
                if m+value>0:
                    flag[i]=1
        if flag[i]:
            break
flaglst=set([i for i in range(len(flag)) if flag[i]==1])
stack=[[1,0,set([i]),0]]
while stack:
    p,m,visited,flag=stack.pop()
    for np,value in data[p]:
        if np in flaglst:
            flag=1
        if np==N:
            if flag:
                print("inf")
                exit()
            else:
                ac.append(m+value)
        if not np in visited:
            tempvisited=copy.copy(visited)
            tempvisited.add(np)
            stack.append([np,m+value,tempvisited,flag])
print(max(ac))

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])

stack=[[1,0,0,{1:0}]]#p,nagasa,visited,flag
ac=[]
while stack:
    p,m,flag,dic=stack.pop()
    for np,value in data[p]:
        if not flag and np in dic and m+value>dic[np]:
            flag=1
            if N in dic:
                print("inf")
                exit()
        if np==N:
            if not flag:
                ac.append(m+value)
            else:
                print("inf")
                exit()
        if not np in dic:
            tempm=m+value
            dic1=copy.copy(dic)
            dic1.update({np:tempm})
            stack.append([np,tempm,flag,dic1])
print(max(ac))

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])

stack=[[1,0,0,{1:0}]]#p,nagasa,visited,flag
ac=[]
while stack:
    p,m,flag,dic=stack.pop()
    if not flag:
        for np,value in data[p]:
            if np in dic and m+value>dic[np]:
                flag=1
                if N in dic:
                    print("inf")
                    exit()
                break
    for np,value in data[p]:
        if np==N:
            if not flag:
                ac.append(m+value)
            else:
                print("inf")
                exit()
        if not np in dic:
            tempm=m+value
            dic1=copy.copy(dic)
            dic1.update({np:tempm})
            stack.append([np,tempm,flag,dic1])
print(max(ac))

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])

stack=[[1,0,0,{1:0}]]#p,nagasa,visited,flag
ac=[]
while stack:
    p,m,flag,dic=stack.pop()
    if not flag:
        for np,value in data[p]:
            if np in dic and m+value>dic[np]:
                flag=1
                if N in dic:
                    print("inf")
                    exit()
                break
    for np,value in data[p]:
        if np==N:
            if not flag:
                ac.append(m+value)
            else:
                print("inf")
                exit()
        if not np in dic:
            tempm=m+value
            dic=copy.copy(dic)
            dic.update({np:tempm})
            stack.append([np,tempm,flag,dic])
print(max(ac))

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])

stack=[[1,0,set([1]),0,{1:0}]]#p,nagasa,visited,flag
ac=[]
while stack:
    p,m,miti,flag,dic=stack.pop()
    if not flag:
        for np,value in data[p]:
            if np in miti and m+value>dic[np]:
                flag=1
                if N in miti:
                    print("inf")
                    exit()
                break
    for np,value in data[p]:
        if np==N:

            if not flag:
                ac.append(m+value)
            else:
                print("inf")
                exit()
        if not np in miti:
            tempm=m+value
            tempmiti=copy.copy(miti)
            tempmiti.add(np)
            dic=copy.copy(dic)
            dic.update({np:tempm})
            stack.append([np,tempm,tempmiti,flag,dic])
print(max(ac))

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])

stack=[[1,0,set([1]),0,{1:0}]]#p,nagasa,visited,flag
ac=[]
while stack:
    p,m,miti,flag,dic=stack.pop()
    if not flag:
        for np,value in data[p]:
            if np in miti and m+value>dic[p]:

                flag=1
                if N in miti:

                    print("inf")
                    exit()
                break
    for np,value in data[p]:
        if np==N:

            if not flag:
                ac.append(m+value)
            else:
                print("inf")
                exit()
        if not np in miti:
            tempm=m+value
            tempmiti=copy.copy(miti)
            tempmiti.add(np)
            dic=copy.copy(dic)
            dic.update({np:tempm})
            stack.append([np,tempm,tempmiti,flag,dic])
print(max(ac))

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])

stack=[[1,0,set([1]),0]]#p,nagasa,visited,flag
ac=[]
while stack:
    p,m,miti,flag=stack.pop()
    if not flag:
        for np,value in data[p]:
            if np in miti:
                flag=1
                if N in miti:
                    print("inf")
                    exit()
                break
    for np,value in data[p]:
        if np==N:

            if not flag:
                ac.append(m+value)
            else:
                print("inf")
                exit()
        if not np in miti:
            tempmiti=copy.copy(miti)
            tempmiti.add(np)
            stack.append([np,m+value,tempmiti,flag])
print(max(ac))

Submission status: Wrong Answer

Solution code:
def bell(edges, n):
    count = 0
    dist = [-10000000000000000 for i in range(n)]
    dist[0] = 0
 
    changed = True
 
    while changed:
        count  += 1
        if count == 500000:
            print('inf')
            exit()
        changed = False
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                changed = True
            dist[edge[1]] = max(dist[edge[0]] + edge[2], dist[edge[1]])
                
    return dist
 
 
n,m = map(int,input().split())
edges = []
for _ in range(m):
    a, b, c = (int(x) for x in input().split())
    edges.append([a-1, b-1, c])
 
res = bell(edges, n)
 
print(res[n-1])

Submission status: Wrong Answer

Solution code:
INF = 10 ** 18
N, M = map(int, input().split())
abc = []
d = [INF] * N
d[0] = 0
loop = [False] * N

for i in range(M):
    a, b, c = map(int, input().split())
    abc.append([a - 1, b - 1,  -1 * c])

for j in range(N):
    for i in range(M):
        if d[abc[i][0]] != INF and d[abc[i][1]] > d[abc[i][0]] + abc[i][2]:
            d[abc[i][1]] = d[abc[i][0]] + abc[i][2]
ans = -1 * d[-1]
for i in range(N):
    for j in range(M):
        if d[abc[j][1]] > d[abc[j][0]] + abc[j][2]:
            d[abc[j][1]] = d[abc[j][0]] + abc[j][2]
            loop[abc[j][1]] = True
        if loop[abc[j][0]] == True:
            loop[abc[j][1]] = True

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**10
def search(graph, n, m):
    d = deque()
    for edge in graph[0]:
        d.append(edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    loop = [0 for i in range(n)]
    while(d):
        # print(d)
        point, cur, nxt = d.popleft()
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                d.append(edge)

            cnt += 1
            if cnt > n:
                loop[nxt] = 1

        if cnt >= n * 2:
            break
    # print(loop)
    if loop[n-1]:
        return "inf"

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    # print(graph)
    ans = search(graph, n, m)

    print(ans)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**10
def search(graph, n, m):
    d = deque()
    for edge in graph[0]:
        d.append(edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    loop = [0 for i in range(n)]
    while(d):
        # print(d)
        point, cur, nxt = d.popleft()
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                d.append(edge)

            cnt += 1
            if cnt > n:
                loop[nxt] = 1

        if cnt >= n * 2:
            break
    # print(loop)
    if loop[n-1]:
        return -INF

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    # print(graph)
    ans = search(graph, n, m)

    print(ans if ans != -INF else "inf")


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**10
def search(graph, n, m):
    d = deque()
    for edge in graph[0]:
        d.append(edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    loop = [0 for i in range(n)]
    while(d):
        print(d)
        point, cur, nxt = d.popleft()
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                d.append(edge)

            cnt += 1
            if cnt > n:
                loop[nxt] = 1

        if cnt >= n * 2:
            break
    print(loop)
    if loop[n-1]:
        return -INF

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    print(graph)
    ans = search(graph, n, m)

    print(ans if ans != -INF else "inf")


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**10
def search(graph, n, m):
    d = deque()
    for edge in graph[0]:
        d.append(edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    loop = [0 for i in range(n)]
    while(d):
        point, cur, nxt = d.popleft()
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                d.append(edge)

            cnt += 1
            if cnt > n:
                loop[nxt] = 1

        if cnt >= n * 2:
            break
    if loop[n-1]:
        return -1

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    ans = search(graph, n, m)

    print(ans if ans != -1 else "inf")


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**10
def search(graph, n, m):
    d = []
    for edge in graph[0]:
        heapq.heappush(d, edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    loop = [0 for i in range(n)]
    while(d):
        point, cur, nxt = heapq.heappop(d)
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                heapq.heappush(d, edge)

            cnt += 1
            if cnt > n:
                loop[nxt] = 1

        if cnt >= n * 2:
            break
    if loop[n-1]:
        return -1
    
    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    ans = search(graph, n, m)

    print(ans if ans != -1 else "inf")


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**10
def search(graph, n, m):
    d = []
    for edge in graph[0]:
        heapq.heappush(d, edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    while(d):
        point, cur, nxt = heapq.heappop(d)
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                heapq.heappush(d, edge)

            cnt += 1
            if cnt > n * 2 and nxt == n-1:
                return -1
            
        if cnt >= n * 3:
            return score[n-1]

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    ans = search(graph, n, m)

    print(ans if ans != -1 else "inf")


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**10
def search(graph, n, m):
    d = []
    for edge in graph[0]:
        heapq.heappush(d, edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    while(d):
        point, cur, nxt = heapq.heappop(d)
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                heapq.heappush(d, edge)

            cnt += 1
            if cnt > n * 2 and nxt == n-1:
                return -1

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    ans = search(graph, n, m)

    print(ans if ans != -1 else "inf")


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**10
def search(graph, n, m):
    d = []
    for edge in graph[0]:
        heapq.heappush(d, edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    while(d):
        point, cur, nxt = heapq.heappop(d)
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                heapq.heappush(d, edge)

            cnt += 1
        if cnt > n * 2:
            return -1

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    ans = search(graph, n, m)

    print(ans if ans != -1 else "inf")


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**10
def search(graph, n):
    d = []
    for edge in graph[0]:
        heapq.heappush(d, edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    while(d):
        point, cur, nxt = heapq.heappop(d)
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                heapq.heappush(d, edge)

        cnt += 1
        if cnt > n * 2:
            return -1

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    ans = search(graph, n)

    print(ans if ans != -1 else "inf")


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
def bell(edges, n):
    count = 0
    dist = [-10000000000000000 for i in range(n)]
    dist[0] = 0
 
    changed = True
 
    while changed:
        count  += 1
        if count == 1000000:
            print('inf')
            exit()
        changed = False
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                changed = True
            dist[edge[1]] = max(dist[edge[0]] + edge[2], dist[edge[1]])
                
    return dist
 
 
n,m = map(int,input().split())
edges = []
for _ in range(m):
    a, b, c = (int(x) for x in input().split())
    edges.append([a-1, b-1, c])
 
res = bell(edges, n)
 
print(res[n-1])

Submission status: Wrong Answer

Solution code:
def bell(edges, n):
    count = 0
    dist = [float('inf') for i in range(n)]
    dist[0] = 0

    changed = True

    while changed:
        count  += 1
        if count == 500000:
            print('inf')
            exit()
        changed = False
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                changed = True
                
    return dist


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

res = bell(edges, n)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def bellmanFord(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    for _ in range(n):
        updated = False
        for v in range(n):
            for u,c in e[v]:
                if d[v]!=inf and d[u]>d[v]+c:
                    d[u] = d[v]+c
                    updated = True
        if not updated:
            break

    loop = False
    d2 = [0]*n
    for i in range(n):
        updated = False
        for v in range(n):
            for u,c in e[v]:
                if d2[v]!=inf and d2[u]>d2[v]+c:
                    d2[u] = d2[v]+c
                    updated = True
        if not updated:
            break
        elif i==n-1:
            loop = True
    return d,loop


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

d,loop = bellmanFord(e,n,0)
if loop:
    print("inf")
else:
    print(-d[n-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def bellmanFord(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    for _ in range(n):
        updated = False
        for v in range(n):
            for u,c in e[v]:
                if d[v]!=inf and d[u]>d[v]+c:
                    d[u] = d[v]+c
                    updated = True
        if not updated:
            break

    loop = False
    d2 = [0]*n
    for i in range(n):
        updated = False
        for v in range(n):
            for u,c in e[v]:
                if d[v]!=inf and d[u]>d[v]+c:
                    d[u] = d[v]+c
                    updated = True
        if not updated:
            break
        elif i==n-1:
            loop = True
    return d,loop


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

d,loop = bellmanFord(e,n,0)
if loop:
    print("inf")
else:
    print(-d[n-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def bellmanFord(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    cnt = 0
    while cnt<2*n:
        updated = False
        for v in range(n):
            for u,c in e[v]:
                if d[v]!=inf and d[u]>d[v]+c:
                    d[u] = d[v]+c
                    updated = True
        if not updated:
            break
        cnt += 1
    return d,cnt==2*n


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

d,loop = bellmanFord(e,n,0)
if loop:
    print("inf")
else:
    print(-d[n-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def bellmanFord(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    cnt = 0
    while cnt<=n:
        updated = False
        for v in range(n):
            for u,c in e[v]:
                if d[v]!=inf and d[u]>d[v]+c:
                    d[u] = d[v]+c
                    updated = True
        if not updated:
            break
        cnt += 1
    return d,cnt==n+1


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

d,loop = bellmanFord(e,n,0)
if loop:
    print("inf")
else:
    print(-d[n-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def bellmanFord(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    cnt = 0
    while True:
        updated = False
        for v in range(n):
            for u,c in e[v]:
                if d[v]!=inf and d[u]>d[v]+c:
                    d[u] = d[v]+c
                    updated = True
        if not updated:
            break
        cnt += 1
        if cnt==n-1:
            break
    return d,cnt==n-1


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

d,loop = bellmanFord(e,n,0)
if loop:
    print("inf")
else:
    print(-d[n-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
vve = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b,e in vve:
  graph[a].append((b,-e))
score = [10**15 for i in range(n+1)]
score[1] = 0
for j in range(n+1):
  flg = 0
  for i in range(m):
    v1,v2,e = vve[i]
    e = -e
    if score[v1] != 10**15 and score[v2] > score[v1]+e:
      score[v2] = score[v1]+e
      flg = 1
      if j == n:
        print("inf")
        exit()
  if flg == 0:
    break
print(-score[n])

Submission status: Wrong Answer

Solution code:
class BellmanFord:
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, start, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf') for i in range(self.N)]
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True, d
        return False, d

n,m = map(int,input().split())
bellman = BellmanFord(n)
for _ in range(m):
    a,b,c = map(int,input().split())
    bellman.add(a-1, b-1, -c, directed=True)

flag, d = bellman.BellmanFord_negative_bool(0, m-1)
if flag:
    print("inf")
else:
    print(-d[-1])

Submission status: Wrong Answer

Solution code:
def BellmanFord(sv, ev, cv, num_v, source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  #辺の緩和
  for i in range(num_v):
    for s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i == num_v-1 and e == num_v-1:
          return "inf"
  
  return dist[-1]*-1

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1))