#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

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

int INF = (1 << 30) - 1;

int n, m;
vector<pair<int, int>> v[50005];
int ciclu = 0;
queue<int> q;
bitset <50005> inqueue(false);
vector <int> dist(50005, INF), cnt(50005, 0);

int main()
{
    in>>n>>m;

    int x, y, c;
    for(int i = 1; i<=m; i++)
    {
        in>>x>>y>>c;
        v[x].push_back({y, c});
    }

    dist[1] = 0;
    q.push(1);
    inqueue[1].flip();

    while(!q.empty() && !ciclu)
    {
        x = q.front();

        q.pop();

        inqueue[x] = false;

        /*vector < pair <int, int> >::iterator it;

        for (it = v[x].begin(); it != v[x].end(); ++ it) if (dist[x] < INF)
            if (dist[it->first] > dist[x] + it->second) {
                dist[it->first] = dist[x] + it->second;
                if (!inqueue[it->first]) {
                    if (cnt[it->first] > n)
                        ciclu = true;
                    else {
                        q.push(it->first);
                        inqueue[it->first] = true;
                        cnt[it->first] ++;
                    }
                }
            }*/

        for(auto i: v[x])
        {
            if(dist[x] < INF)
            {
                if(dist[i.first] > dist[x] + i.second)
                {
                    dist[i.first] = dist[x] + i.second;
                    if(!inqueue[i.first])
                    {
                        if(cnt[i.first] > n)
                        {
                            ciclu = true;
                        }
                        else
                        {
                            q.push(i.first);
                            inqueue[i.first] = true;
                            cnt[i.first]++;
                        }
                    }
                }
            }
        }
    }

    if(ciclu == 1)
    {
        out<<"Ciclu negativ!";
    }
    else
    {
        for(int i = 2; i<=n; i++)
        {
            out<<dist[i]<<" ";
        }
    }

    return 0;
}