#include <bits/stdc++.h>
#define MAX 50003

using namespace std;

int d[MAX], n, m;
vector < pair <int, int> > G[MAX];
queue <int> Q;
int nr[MAX];
bool inQ[MAX];
void init()
{
    int i;
    for(i = 1; i <= n; i ++) d[i] = INT_MAX;
    d[1] = 0;
}
bool bellman()
{
    int i, nod, x;
    bool negativ = false;
    Q.push(1);
    while(!Q.empty() && !negativ)
    {
        nod = Q.front();
        Q.pop();
        inQ[nod] = false;
        x=G[nod].size();
        for(i = 0; i < x && !negativ; i ++)
        if(d[G[nod][i].first] > d[nod] + G[nod][i].second)
        {
            d[G[nod][i].first] = d[nod] + G[nod][i].second;
            if(!inQ[G[nod][i].first])
                {
                    if(nr[G[nod][i].first] < n)
                                {
                                    Q.push(G[nod][i].first);
                                    nr[G[nod][i].first] ++;
                                    inQ[G[nod][i].first] = true;
                                } else negativ = true;
                }
        }
    }
    return negativ;
}
int main()
{
    int x, y, c, i;
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        f >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }
    init();
    if(bellman()) g << "Ciclu negativ!\n";
      else for(i = 2; i <= n; i ++) g << d[i] << " ";
    return 0;
}