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

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

struct edge
{
    int from;
    int to;
    int cost;
};

const int N=50000;
const int M=250000;
const int INF=9000000;

std::queue<int> q;

std::vector<int> v[N+1];
edge g[M+1];

int d[N+1];
int relax_counter[N+1];
bool inqueue[N+1];

int n, m;

int main()
{
    in>>n>>m;
    for(int it=1; it<=m; it++)
    {
        in>>g[it].from>>g[it].to>>g[it].cost;
        v[g[it].from].push_back(it);
    }

    for(int it=1; it<=n; it++)
    {
        d[it]=INF;
    }
    d[1]=0;

    q.push(1);
    inqueue[1]=1;
    while(!q.empty())
    {
        int curr=q.front();
        q.pop();
        inqueue[curr]=0;

        for(int edg : v[curr])
        {
            int to=g[edg].to;
            int cost=g[edg].cost;

            if(d[to]>d[curr]+cost)
            {
                d[to]=d[curr]+cost;
                if(!inqueue[to])
                {
                    q.push(to);
                    inqueue[to]=true;
                    relax_counter[to]++;

                    if(relax_counter[to]==n)
                    {
                        out<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for(int i=2; i<=n; i++)
    {
        out<<d[i]<<" ";
    }
}