def printSolution(numOfVertices, distance):
    for i in range(numOfVertices):
        for j in range(numOfVertices):
              print(distance[i][j], end="  ")
        print(" ")

def floydWarshall(numOfVertices, G):
    distance = G
    for k in range(numOfVertices):
        for i in range(numOfVertices):
            for j in range(numOfVertices):
                distance[i][j] = max(distance[i][j], distance[i][k]+distance[k][j])


    print(max(max(i) for i in G))

v=int(input("Enter vertices"))
G=[[float('-inf')]*v for i in range(v)]

e=int(input("Enter edge count"))
print("enter u,v,w")
for _ in range(e):
    u,v,w=input().split()
    u,v,w=int(u)-1,int(v)-1,float(w)
    G[u][v]=w

for i in range(v):
    G[i][i]=0

floydWarshall(v+2, G)