|
| 1 | +importsys |
| 2 | +input=sys.stdin.readline |
| 3 | +INF=int(1e9)# 무한을 의미하는 값으로 10억을 설정 |
| 4 | + |
| 5 | +# 노드의 개수, 간선의 개수를 입력받기 |
| 6 | +n,m=map(int,input().split()) |
| 7 | +# 모든 간선에 대한 정보를 담는 리스트 만들기 |
| 8 | +edges= [] |
| 9 | +# 최단 거리 테이블을 모두 무한으로 초기화 |
| 10 | +distance= [INF]* (n+1) |
| 11 | + |
| 12 | +# 모든 간선 정보를 입력받기 |
| 13 | +for_inrange(m): |
| 14 | +a,b,c=map(int,input().split()) |
| 15 | +# a번 노드에서 b번 노드로 가는 비용이 c라는 의미 |
| 16 | +edges.append((a,b,c)) |
| 17 | + |
| 18 | +defbf(start): |
| 19 | +# 시작 노드에 대해서 초기화 |
| 20 | +distance[start]=0 |
| 21 | +# 전체 n - 1번의 라운드(round)를 반복 |
| 22 | +foriinrange(n): |
| 23 | +# 매 반복마다 "모든 간선"을 확인하며 |
| 24 | +forjinrange(m): |
| 25 | +cur_node=edges[j][0] |
| 26 | +next_node=edges[j][1] |
| 27 | +edge_cost=edges[j][2] |
| 28 | +# 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 |
| 29 | +ifdistance[cur_node]!=INFanddistance[next_node]>distance[cur_node]+edge_cost: |
| 30 | +distance[next_node]=distance[cur_node]+edge_cost |
| 31 | +# n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재 |
| 32 | +ifi==n-1: |
| 33 | +returnTrue |
| 34 | +returnFalse |
| 35 | + |
| 36 | +# 벨만 포드 알고리즘을 수행 |
| 37 | +negative_cycle=bf(1)# 1번 노드가 시작 노드 |
| 38 | + |
| 39 | +ifnegative_cycle: |
| 40 | +print("-1") |
| 41 | +else: |
| 42 | +# 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력 |
| 43 | +foriinrange(2,n+1): |
| 44 | +# 도달할 수 없는 경우, -1을 출력 |
| 45 | +ifdistance[i]==INF: |
| 46 | +print("-1") |
| 47 | +# 도달할 수 있는 경우 거리를 출력 |
| 48 | +else: |
| 49 | +print(distance[i]) |