이번 문제는 플로이드-와샬 알고리즘을 통해 모든 정점에서 모든 정점으로의 최단 거리를 구하고, 이를 이용하여 사이클의 유무를 확인하는 방식으로 해결하였다.

Code

v, e=map(int, input().split())
grid=[[1e9 for _ in range(v+1)] for _ in range(v+1)]
for _ in range(e):
    a, b, c=map(int, input().split())
    grid[a][b]=min(grid[a][b], c)
for k in range(1, v+1):
    for i in range(1, v+1):
        for j in range(1, v+1):
            if i==j:
                grid[i][j]=0
            grid[i][j]=min(grid[i][k]+grid[k][j], grid[i][j])
path=[]
ans=1e9
for i in range(1, v+1):
    for j in range(i+1, v+1):
        ans=min(ans, grid[i][j]+grid[j][i])
if ans==1e9:
    ans=-1
print(ans)