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

using namespace std;

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

int n, m, ok;
const int nmax = 50005, val_mare = 50000000;
vector<pair<int, int> > list_vec[nmax];

int dist[nmax];
struct muchie
{
    int u, v, c;
};
muchie MC[250005];

void bellman(int start)
{
    int i, j;

    for(i = 1; i <= n; ++i)
        dist[i] = val_mare;
    dist[start] = 0;

    for(i = 1; i < n; ++i)
    {
        ok = 0;
        for(j = 1; j <= m; ++j)
        {
            if(dist[MC[j].v] > dist[MC[j].u] + MC[j].c)
            {
                ok = 1;
                dist[MC[j].v] = dist[MC[j].u] + MC[j].c;
            }
        }
        if(!ok)
            break;
    }
}
int main()
{
    int u, v, c, i;
    fin>>n>>m;

    for(i = 1; i <= m; ++i)
        fin>>MC[i].u>>MC[i].v>>MC[i].c;

    bellman(1);

    if(ok)
        fout<<"Ciclu negativ!";
    else
    {
        for(i = 2; i <= n; ++i)
            fout<<dist[i]<<' ';
    }
    return 0;
}