BOJ - 1865 - K번째 최단경로 찾기

import sys


def bellmanFord(dist, adjList, N, isPossible):

    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for w, v in adjList[j]:
                if dist[v] > w + dist[j]:
                    dist[v] = w + dist[j]
                    if i == N:
                        isPossible[0] = False


def solution():
    TC = int(sys.stdin.readline())
    for _ in range(TC):
        N, M, W = map(int, sys.stdin.readline().split())
        INF = 1e9
        dist = [INF for _ in range(N + 1)]
        adjList = [[] for _ in range(N + 1)]

        for _ in range(M):
            S, E, T = map(int, sys.stdin.readline().split())
            adjList[S].append((T, E))
            adjList[E].append((T, S))

        for _ in range(W):
            S, E, T = map(int, sys.stdin.readline().split())
            adjList[S].append((-T, E))

        isPossible = [True]
        bellmanFord(dist, adjList, N, isPossible)
        print("NO" if isPossible[0] else "YES")

solution()

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