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

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

const int nmax = 50008;
const int inf = 1<<30;

struct NOD{int y, cost;};
int N, M;
vector <NOD> G[nmax];
queue <int> q;
int d[nmax];

void read()
{
    int x, y, cost;
    fin>>N>>M;
    for(int i = 1; i <= M; i++)
    {
        fin>>x>>y>>cost;
        G[x].push_back((NOD){y,cost});
    }
}

bool BellmanFord(int r)
{
    int viz[nmax], y;
    for(int i =1 ;i <= N; i++)
        viz[i] = 0, d[i] = inf;
    d[r] = 0;
    q.push(r);
    while(!q.empty())//cat timp mai avem noduri de vizitat
    {
        int  x = q.front();//alegem un nod
        q.pop();   viz[x]++; //ii marcam vizita si il scoatem din coada nodurilor care pot amelioara drumurile

        if(viz[x] == N)   return false; //daca nodul actual a mai fost ales de N ori insemna ca graful contine cicluri negative,pt ca nu poti imbunatati un drum la un nod D N ori cu doar N noduri

        for(vector<NOD>::iterator it = G[x].begin(); it!= G[x].end(); it++)
        {
            int y = (*it).y;
            if(d[x] + (*it).cost < d[y])//daca distanta de la radacina pana la nodul nou imbunatati + o muchie pana la alt nod< distanta de la rad pana la nodu resp
            {
                d[y] = d[x] + (*it).cost;//actualizam costul
                q.push(y);//punem nodul in coada, acesta avand un cost mai mic de la radacina pana la el, deci putand imbnatati alte drumuri
            }
        }
    }
    return true;
}
int main()
{
    read();
    if(BellmanFord(1) ==true)
        for(int i = 2; i <= N; i++)
            fout << d[i]<<" ";
     else
        fout<<"Ciclu negativ!";
    fin.close();
    return 0;
}