#include <fstream>
#include <string.h>
#include <vector>


using namespace std;
const int Nmax = 50005;
const int INF = 0x3f3f3f3f;

int dist[Nmax];
vector<pair<int, int>> G[Nmax];

int main()
{
    ifstream f ("bellmanford.in");
    ofstream g ("bellmanford.out");

    int N, M, a, b, d;
    f >> N >> M;
    for (int i = 0; i < M; i++)
    {
        f >> a >> b >> d;
        G[a].push_back(make_pair(b, d));
    }
    
    memset(dist, INF, sizeof(dist));

    dist[1] = 0;
    for (int n = 1; n < N; n++)
    for (int a = 1; a <= N; a++)
    {
        for (auto P: G[a])
            if (dist[P.first] > dist[a] + P.second)
                dist[P.first] = dist[a] + P.second;
    }

    bool good = 1;
    for (int a = 1; a <= N && good; a++)
        for (auto P: G[a])
            if (dist[P.first] > dist[a] + P.second)
                { good = 0; break; }


    if (good)
        for (int a = 2; a <= N; a++)
            g << dist[a] << ' ';
    else
        g << "Ciclu negativ!";
    
    g << '\n';

    return 0;
}