#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
//vector < pair <int, int> > a[1001];
int n, m, c[1001][1001], d[1001], inf = 9999;
int a[1001][1001];

void citire()
{
    fin>>n>>m;
    int x, y, co;
    while(fin>>x>>y>>co)
    {
        a[x][y] = 1;
        c[x][y] = co;
        //a[x].push_back(make_pair(y, c));
    }
}

void init(int s)
{
    for(int i=1; i<=n; i++)
    {
        d[i] = inf;
    }
    d[s] = 0;
}

void relax(int u, int v)
{
    if(d[v]>d[u]+c[u][v])
    {
        d[v] = d[u] + c[u][v];
    }
}

int bellamn_ford(int s)
{
    init(s);
    int i, j, k;
    for(i=1; i<=n-1; i++)
    {
        for(j=1; j<=n; j++)
        {
            for(k=1; k<=n; k++)
            {
                if(a[j][k] == 1)
                {
                    relax(j, k);
                }
            }
        }
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(a[i][j] == 1)
            {
                if(d[j] > d[i] + c[i][j])
                    return 0;
            }
        }
    }
    return 1;
}

int main()
{
    citire();
    if(bellamn_ford(1))
    {
        int i;
        for(i=2; i<=n; i++)
            fout<<d[i]<<" ";
    }
    else
        fout<<"Ciclu negativ!";
    return 0;
}