ベルマンフォード法

ある一点からスタートし、そこから残りの全ての頂点に達するのに必要な最短コストを計算するときに使える。計算量は、頂点V、辺の数EとしてO(VE)。負の辺があっても使えるのが、ダイクストラ法と違うところ（強み）。

構造は単純で、頂点の数vから1引いた数だけループを回す。つまり、始点以外のv-1個の頂点に対して最短経路を出すには、多くてもv-1回回せば十分ということだ。それ以上やっても更新できない（逆に、更新できてしまったら、ループ上を周回することで無限にコストを小さくすることができる「負のループ」が存在することになってしまう）。
そして、多くてもv-1回のループに対して、すべての辺を参照する。始点と繋がってる頂点から伸びた辺を介して、到達可能な点がじわじわ増えていく印象。全ての辺を見ても更新がなければ、もうそれで最短経路が確定しているのでそこでループを打ち切って、答えを出力する。（ここの省エネがないと結構時間がかかったりする）

judge.u-aizu.ac.jp

答え↓

v,e,r = map(int,input().split()) #v:頂点数、e:辺数、r:始点
D = [float('inf')]*v #D[i]は始点rからiの最短距離を表す、0インデックス
L = []
find_negative = False #負のループ検出
for i in range(e):
    s,t,d = map(int,input().split()) #s:始点、t:終点、d:コスト
    L.append([s,t,d])
D[r] = 0 #スタート地点はコスト0で到達可能
for i in range(v):
    update = False #辺の更新判定
    for j in range(e):
        a,b,c = L[j][0],L[j][1],L[j][2] #a,b,cはs,t,dに相当
        if D[b] > D[a]+c: #bに到達するのに、aを介した方がいいとなれば
            D[b] = D[a]+c コストを更新
            update = True
            if i == v-1: #v回のループでまだ更新があるようであれば、
                find_negative = True #負のループが存在する
                break
    if not update: #全ての辺を見ても最短経路の更新がなければ
        break #これ以上やる意味がないのでここでループを抜ける
if find_negative:
    print('NEGATIVE CYCLE')
else:
    for i in range(v):
        if D[i] == float('inf'):
            print('INF')
        else:
            print(D[i])