CodeEff/ECCO huggingface dataset:
# Original solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=set([0]+f);Y=set(X);R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):a,b,c=I();R+=[((a,b),c)];Y.add(c);X.add(a);X.add(b)
for i in r(m):a,b,c=I();H+=[(a,(b,c))];X.add(a);Y.add(b);Y.add(c)
s=dict(enumerate(sorted(X)));K=len(s);t=dict(enumerate(sorted(Y)));L=len(t);h=dict(list(zip(list(s.values()),list(s.keys()))));w=dict(list(zip(list(t.values()),list(t.keys()))));V=[[0]*-~K for i in r(L+1)];U=[i[:]for i in V];v=[i[:]for i in V]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j]
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for j in r(K):
 for i in r(L):V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(K>c>=0<=d<L)*v[d][c]==0:
   if U[(f>0)+y][x]|e==0 or V[y][(e>0)+x]|f==0:q+=[(c,d)];v[d][c]=1
if a>F:a='INF'
print(a)


# Optimized solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):a,b,c=I();R+=[((a,b),c)];Y+=[c];X+=[a,b]
for i in r(m):a,b,c=I();H+=[(a,(b,c))];X+=[a];Y+=[b,c]
s=dict(enumerate(sorted(set(X))));K=len(s);t=dict(enumerate(sorted(set(Y))));L=len(t);h=dict(list(zip(list(s.values()),list(s.keys()))));w=dict(list(zip(list(t.values()),list(t.keys()))));V=[[0]*-~K for i in r(L+1)];U=[i[:]for i in V];v=[i[:]for i in V]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for i in r(L+1):
 for j in r(K):U[i][j+1]+=U[i][j]
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for j in r(K+1):
 for i in r(L):V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(K>c>=0<=d<L)*v[d][c]==0:
   if U[(f>0)+y][x]|e==0 or V[y][(e>0)+x]|f==0:q+=[(c,d)];v[d][c]=1
if a>F:a='INF'
print(a)
# Original solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):a,b,c=I();R+=[((a,b),c)];Y+=[c];X+=[a,b]
for i in r(m):a,b,c=I();H+=[(a,(b,c))];X+=[a];Y+=[b,c]
def g(X):
 s=dict(enumerate(sorted(set(X))));K=len(s);h={s[i]:i for i in s}
 return s,K,h
s,K,h=g(X);t,L,w=g(Y);V=[[0]*-~K for i in r(L+1)];U=[i[:]for i in V];v=[i[:]for i in V]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(K>c>=0<=d<L)*v[d][c]==0:
   if U[(f>0)+y][x]|e==0 or V[y][(e>0)+x]|f==0:q+=[(c,d)];v[d][c]=1
if a>F:a='INF'
print(a)

# Optimized solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):a,b,c=I();R+=[((a,b),c)];Y+=[c];X+=[a,b]
for i in r(m):a,b,c=I();H+=[(a,(b,c))];X+=[a];Y+=[b,c]
def g(X):
 s=dict(enumerate(sorted(set(X))));K=len(s);h={s[i]:i for i in s}
 return s,K,h
s,K,h=g(X);t,L,w=g(Y);V=[[0]*(K+2)for i in r(L+2)];U=[i[:]for i in V];v=[i[:]for i in V]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L+1):
 for j in r(K+1):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(K>c>=0<=d<L)*v[d][c]==0:
   if U[(f>0)+y][x]|e==0 or V[y][(e>0)+x]|f==0:q+=[(c,d)];v[d][c]=1
if a>F:a='INF'
print(a)
# Original solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):a,b,c=I();R+=[((a,b),c)];Y+=[c];X+=[a,b]
for i in r(m):a,b,c=I();H+=[(a,(b,c))];X+=[a];Y+=[b,c]
def g(X):s=dict(enumerate(sorted(set(X))));return s,len(s),{s[i]:i for i in s}
s,K,h=g(X);t,L,w=g(Y);V=[[0]*(K+2)for i in r(L+2)];U=[i[:]for i in V];v=[i[:]for i in V]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L+1):
 for j in r(K+1):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(K>c>=0<=d<L)*v[d][c]==0:
   if U[(f>0)+y][x]|e==0 or V[y][(e>0)+x]|f==0:q+=[(c,d)];v[d][c]=1
if a>F:a='INF'
print(a)

# Optimized solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):a,b,c=I();R+=[((a,b),c)];Y+=[c];X+=[a,b]
for i in r(m):a,b,c=I();H+=[(a,(b,c))];X+=[a];Y+=[b,c]
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*(K+2)for i in r(L+2)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L+1):
 for j in r(K+1):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(K>c>=0<=d<L)*v[d][c]==0:
   if U[(f>0)+y][x]|e==0 or V[y][(e>0)+x]|f==0:q+=[(c,d)];v[d][c]=1
if a>F:a='INF'
print(a)
# Original solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=Y=[0]+f;R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=[(a,c)];Y+=[c];X+=a
for i in r(m):a,*b=I();H+=[(a,b)];X+=[a];Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)+1
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(K>c>=0<=d<L)*v[d][c]==0:
   if U[(f>0)+y][x]|e==0 or V[y][(e>0)+x]|f==0:q+=[(c,d)];v[d][c]=1
if a>F:a='INF'
print(a)

# Optimized solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=[(a,c)];Y+=[c];X+=a
for i in r(m):a,*b=I();H+=[(a,b)];X+=[a];Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)+1
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*(K+1)for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(K>c>=0<=d<L)*v[d][c]==0:
   if U[(f>0)+y][x]|e==0 or V[y][(e>0)+x]|f==0:q+=[(c,d)];v[d][c]=1
if a>F:a='INF'
print(a)
# Original solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=[(a,c)];Y+=c,;X+=a
for i in r(m):a,*b=I();H+=[(a,b)];X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)+1
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0)and 0==v[d][c]:q+=[(c,d)];v[d][c]=1
print(([a,'INF'][a>F]))

# Optimized solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=[(a,c)];Y+=c,;X+=a
for i in r(m):a,*b=I();H+=[(a,b)];X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)+1
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if 0==v[d][c]and(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0):q+=[(c,d)];v[d][c]=1
print(([a,'INF'][a>F]))
# Original solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if 1-v[d][c]and(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0):q+=(c,d),;v[d][c]=1
print(([a,'INF'][a>F]))

# Optimized solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0):q+=(c,d),;v[d][c]=1
print(([a,'INF'][a>F]))
# Original solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0):q+=(c,d),;v[d][c]=1
print(([a,'INF'][a>F]))

# Optimized solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0):q+=[(c,d)];v[d][c]=1
print(([a,'INF'][a>F]))
# Original solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=sorted(set(X));l=len(s);return{s[i]:i for i in r(l)},s,l
h,s,K=g(X);w,t,L=g(Y);V,U,v=[[[0]*-~K for i in r(L+1)]for _ in r(3)]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];a=0
while q:
 x,y=q.pop();v[y][x]=1;a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and U[(f>0)+y][x]*f+V[y][(e>0)+x]*e==0:q+=(c,d),;v[d][c]=1
print(([a,'INF'][a>F]))

# Optimized solution
I=lambda:list(map(int,input().split()));F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=sorted(set(X));l=len(s);return{s[i]:i for i in r(l)},s,l
h,s,K=g(X);w,t,L=g(Y);V,U,v=[[[0]*-~K for i in r(L+1)]for _ in r(3)];q=[(h[0],w[0])];z=0
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
while q:
 x,y=q.pop();v[y][x]=1;z+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and U[(f>0)+y][x]*f+V[y][(e>0)+x]*e==0:q+=[(c,d)];v[d][c]=1
print(([z,'INF'][z>F]))
# Original solution
n,m=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(m)]
distance=[9999999999999999]*n
distance[0]=0
for i in range(n-1):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
f=[0]*n
for i in range(n):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
      f[l[j][1]-1]=1
    if f[l[j][0]-1]==1:
      f[l[j][1]-1]=1
if f[n-1]==0:
  print((-distance[n-1]))
else:
  print('inf')

# Optimized solution
n,m=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(m)]
distance=[float('inf')]*n
distance[0]=0
for i in range(n-1):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
x=distance[n-1]
for i in range(n):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=-float('inf')
if distance[n-1]==x:
  print((-distance[n-1]))
else:
  print('inf')
# Original solution
N, M = list(map(int, input().split()))
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = list(map(int, input().split()))
    adjacent.append([a-1, b-1, c])
for i in range(2*N):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
    if i == N-2:
      t = score[N-1]
    if i == 2*N-1:
      if t != score[N-1]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(t)
else:
    print('inf')

# Optimized solution
N, M = list(map(int, input().split()))
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = list(map(int, input().split()))
    adjacent.append([a-1, b-1, c])
for i in range(N):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
    if i == N-2:
      t = score[N-1]
    if i == N-1:
      if t != score[N-1]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(t)
else:
    print('inf')
# Original solution
N, M = list(map(int, input().split()))
E = []
for _ in range(M):
    a,b,c = list(map(int, input().split()))
    E.append((a,b,c))
dist = [-N*10**9]*(N+1)
dist[1] = 0
flag = False
for i in range(N):
    for (a,b,c) in E:
        newlen = dist[a] + c
        if newlen > dist[b]:
            if i == N-1:
                flag = True
            dist[b] = newlen
            predist = dist[N]

dist2 = dist.copy()
for i in range(N):
    for (a,b,c) in E:
        newlen = dist2[a] + c
        if newlen > dist2[b]:
            dist2[b] = newlen
if dist2[N] > dist[N]:
    print("inf")
else:
    print((dist[N]))

# Optimized solution
N, M = list(map(int, input().split()))
E = []
for _ in range(M):
    a,b,c = list(map(int, input().split()))
    E.append((a,b,c))
dist = [-N*10**9]*(N+1)
dist[1] = 0
flag = False
for i in range(N):
    for (a,b,c) in E:
        newlen = dist[a] + c
        if newlen > dist[b]:
            dist[b] = newlen
    if i == N-1 and dist[N] > predist:
        flag =True
    predist = dist[N]

if flag:
    print("inf")
else:
    print((dist[N]))
# Original solution
N, M = list(map(int, input().split()))
E = []
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a, b = a - 1, b - 1
    c = -c
    E.append([a, b, c])

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

for n in range(N):
    for a, b, c in E:
        if (dist[a] != float('inf')) & (dist[b] > dist[a] + c):
            dist[b] = dist[a] + c
            if (n == N - 1) & (b == N - 1):
                print('inf')
                exit()

print((-dist[N - 1]))


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

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

for i in range(N):
    for fr, to, cost in Edges:
        if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
            dist[to] = dist[fr] + cost
            if (i == N - 1) & (to == N - 1):
                print('inf')
                exit()

print((-dist[-1]))
# Original solution
import sys

stdin = sys.stdin


def na(): return list(map(int, stdin.readline().split()))


def ns(): return stdin.readline().strip()

def bf(es, n, start, ved):
    I = 999999999999999999
    d = [I] * n
    d[start] = 0

    for i in range(n-1):
        updated = False
        for e in es:
            if not ved[e[0]]: continue
            if not ved[e[1]]: continue
            if d[e[0]] + e[2] < d[e[1]]:
                d[e[1]] = d[e[0]] + e[2]
                updated = True
        if not updated: break
    for e in es:
        if not ved[e[0]]: continue
        if not ved[e[1]]: continue
        if d[e[0]] + e[2] < d[e[1]]:
            return None
    return d


n,m = na()
es = []

for i in range(m):
    a,b,c = na()
    es.append([a-1,b-1,-c])

ig = [[] for _ in range(n)]
for e in es:
    ig[e[1]].append(e)

ved = [False] * n
q = [n-1]
j = 0
ved[n-1] = True
while(j < len(q)):
    cur = q[j]
    for e in ig[cur]:
        if not ved[e[0]]:
            ved[e[0]] = True
            q.append(e[0])
    j += 1

res = bf(es, n, 0, ved)
if res:
    print((-res[n-1]))
else:
    print("inf")

# Optimized solution
import sys

stdin = sys.stdin


def na(): return list(map(int, stdin.readline().split()))


def ns(): return stdin.readline().strip()

def bf(es, n, start, ved):
    I = 999999999999999999
    d = [I] * n
    d[start] = 0

    for i in range(n-1):
        updated = False
        for e in es:
            if not ved[e[0]]: continue
            if not ved[e[1]]: continue
            if d[e[0]] + e[2] < d[e[1]]:
                d[e[1]] = d[e[0]] + e[2]
                updated = True
        if not updated: break
    for e in es:
        if not ved[e[0]]: continue
        if not ved[e[1]]: continue
        if d[e[0]] + e[2] < d[e[1]]:
            return None
    return d

def go(start, g, ind):
    n = len(g)
    ved = [False] * n
    q = [start]
    j = 0
    ved[start] = True
    while(j < len(q)):
        cur = q[j]
        for e in g[cur]:
            if not ved[e[ind]]:
                ved[e[ind]] = True
                q.append(e[ind])
        j += 1
    return ved

n,m = na()
es = []

for i in range(m):
    a,b,c = na()
    es.append([a-1,b-1,-c])

g = [[] for _ in range(n)]
for e in es:
    g[e[0]].append(e)

ig = [[] for _ in range(n)]
for e in es:
    ig[e[1]].append(e)


ved = go(0, g, 1)
ived = go(n-1, ig, 0)

for i in range(n):
    ved[i] &= ived[i]

res = bf(es, n, 0, ved)
if res:
    print((-res[n-1]))
else:
    print("inf")
# Original solution
def BellmanFord(edges, 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 edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i == num_v - 1 and edge[1] == num_v:
                    return -1

    return dist

num_v, num_e = list(map(int, input().split()))
edges = []
for _ in range(num_e):
    a, b, c = list(map(int, input().split()))
    edges.append((a, b, -c))

dist = BellmanFord(edges, num_v, 1)
if dist == -1:
    print("inf")
else:
    print((-dist[-1]))


# Optimized solution
def BellmanFord(edges, 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 edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                #負閉経路かつそれがゴールを通るもの、がある
                #i == num_v-1だけだと、負閉経路の検出だけになる
                if i == num_v - 1 and edge[1] == num_v:
                    return -1

    return dist

num_v, num_e = list(map(int, input().split()))
edges = []
for _ in range(num_e):
    a, b, c = list(map(int, input().split()))
    edges.append((a, b, -c))

dist = BellmanFord(edges, num_v, 1)
if dist == -1:
    print("inf")
else:
    print((-dist[-1]))
# Original solution
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))
e = [set() for _ in range(N + 1)]
reve = [[] for _ in range(N + 1)]
for _ in range(M):
  u, v, c = list(map(int, input().split()))
  e[u].add((v, -c))
  reve[v].append(u)

vis = [0] * (N + 1)
def revdfs(x):
  global vis
  if x == 1: return True
  res = 0
  for y in reve[x]:
    if vis[y]: continue
    vis[y] = 1
    res |= revdfs(y)
  return res
def dfs(x):
  global vis
  if x == N: return True
  res = 0
  for y, _ in e[x]:
    if vis[y]: continue
    vis[y] = 1
    res |= dfs(y)
  return res
banned = [0] * (N + 1)
for x in range(1, N + 1):
  vis = [0] * (N + 1)
  banned[x] |= revdfs(x) ^ 1
  vis = [0] * (N + 1)
  banned[x] |= dfs(x) ^ 1

for x in range(1, N + 1):
  t = list(e[x])
  for y, d in t:
    if banned[x] | banned[y]: e[x].discard((y, d))
#print(banned)
INF = 10**18
dist = [INF] * (N + 1)
dist[1] = 0
update = 1
for _ in range(N + 1):
    update = 0
    for v, x in enumerate(e):
        for t, cost in x:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break
else:
  print("inf")
  exit(0)
print((-dist[N]))

# Optimized solution
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))
e = []
for _ in range(M):
  u, v, c = list(map(int, input().split()))
  e.append((u, v, -c))
inf = 10 ** 18
d = [inf] * (N + 1)
d[1] = 0
for _ in range(N - 1):
  for u, v, c in e: d[v] = min(d[v], d[u] + c)
loop = []
for u, v, c in e:
  if d[v] > d[u] + c:
    d[v] = min(d[v], d[u] + c)
    loop.append(v)
if len(loop) == 0:
  print((-d[-1]))
  exit(0)
for v in loop: d[v] = -inf
for _ in range(N - 1):
  for u, v, c in e:
    if v == N and (d[v] > d[u] + c): break
    d[v] = min(d[v], d[u] + c)
  else: continue
  break
else: 
  print((-d[-1]))
  exit(0)
print("inf")