#include <fstream>
#define oo 0x7fffffff
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct muchie
{
    int x, y, c;
} M[250001];

int n, m, dist[50001];

bool bellman()
{
    for (int i = 1; i <= n; i++)
        dist[i] = oo;
    dist[1] = 0;

    for (int i = 1; i < n; i++)
        for (int j = 0; j < m; j++)
            if (dist[M[j].x] != oo)
                dist[M[j].y] = min(dist[M[j].y], dist[M[j].x] + M[j].c);
    for (int j = 0; j < m; j++)
        if (dist[M[j].x] + M[j].c < dist[M[j].y])
            return false;

    return true;
}

int main()
{
    int x, y, c;

    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y >> c;
        M[i].x = x; M[i].y = y; M[i].c = c;
    }

    if(!bellman())
        fout << "Ciclu negativ!";
    else
        for (int i = 2; i <= n; i++)
            fout << dist[i] << ' ';

}