BOJ - 16064 - Coolest Ski Route

import sys
_INF = 1e10

def solution():
    N, M = map(int, sys.stdin.readline().split())

    dist = [[_INF for j in range(N)] for i in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for _ in range(M):
        S, T, C = map(int, sys.stdin.readline().split())
        C *= -1
        if dist[S-1][T-1] != _INF:
            if C < dist[S-1][T-1]:
                dist[S-1][T-1] = C
        else:
            dist[S-1][T-1] = C

    for k in range(N):
        for i in range(N):
            if dist[i][k] == _INF: continue
            for j in range(N):
                if dist[k][j] == _INF: continue
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    print(-min([min(dist[i]) for i in range(N)]))

solution()

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