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

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n, m, ciclu;
vector<pair<int, int>> v[50005];
int dist[50005];
int viz[50005];
int iq[50005];
queue<int> q;
int INF = (1 << 30);

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});
    }

    for(int i = 2; i<=n; i++)
    {
        dist[i] = INF;
    }

    q.push(1);
    viz[1] = 1;
    iq[1] = 1;

    while(!q.empty() && ciclu == 0)
    {
        int nod = q.front();
        viz[nod] = 0;
        q.pop();

        for(auto it: v[nod])
        {
            if(dist[it.first] > dist[nod] + it.second)
            {
                dist[it.first] = dist[nod] + it.second;

                if(viz[it.first] == 0)
                {
                    iq[it.first]++;

                    if(iq[it.first] > n)
                    {
                        ciclu = 1;
                        break;
                    }

                    q.push(it.first);
                    viz[it.first] = 1;
                }
            }
        }
    }

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

    return 0;
}