#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
long long aa[6001];
typedef struct _edges
{
    int from;
    int to;
    int cost;
} Edges;
Edges edges[6001];

int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        aa[i] = INF;
    }
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i].from = a;
        edges[i].to = b;
        edges[i].cost = c;
    }
    aa[1] = 0;
    for (int j = 0; j < n; j++)
    {

        for (int i = 0; i < m; i++)
        {
            if (aa[edges[i].from] != INF && aa[edges[i].to] > aa[edges[i].from] + edges[i].cost)
            {
                aa[edges[i].to] = aa[edges[i].from] + edges[i].cost;
                if (j == n - 1)
                {
                    cout << -1;
                    return 0;
                }
            }
        }
    }

    for (int i = 2; i <= n; i++)
    {
        if (aa[i] >= INF)
        {
            aa[i] = -1;
        }
        cout << aa[i] << "\n";
    }

    return (0);
}

벨만포드 알고리즘이다

틀린 이유

• long long 으로 해주어야 한다.
• aa[edges[i].from] != INF 라는 조건을 추가해 줘야한다. 이어 지지 않았는데 만약 cost 가 음수면 INF+ cost 가 값이 더 작으므로 값이 업데이트된다.
• 음수 사이클을 체크 해줘야 한다.