BOJ - 1956 - 운동

import sys

def solution():
    V, E = map(int, sys.stdin.readline().split())
    graph = [[1e9 for _ in range(V)] for _ in range(V)]
    for _ in range(E):
        a, b, c = map(int, sys.stdin.readline().split())
        graph[a-1][b-1] = c

    for k in range(V):
        for i in range(V):
            for j in range(V):
                graph[i][j] = min(
                    graph[i][j], graph[i][k] + graph[k][j]
                )

    result = 1e9
    for i in range(V):
        result = min(result, graph[i][i])

    if result == 1e9: print(-1)
    else: print(result)

solution()

https://www.acmicpc.net/problem/1956