#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 1e9
#define nmax 50005
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m, d[nmax], viz[nmax];
vector <pair <int,int> > v[nmax];
queue  <int> q;

void citire()
{
    int i,j,k,c;
    f>>n>>m;
    for(k=1; k<=m; k++)
    {
        f>>i>>j>>c;
        v[i].push_back({j, c});
    }
}

void bellman()
{
    int k,nod, cost, vec;
    for(k=1; k<=n; k++) d[k]=inf;
    d[1]=0;
    q.push(1);
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        viz[nod]=0;
        for(k=0; k<v[nod].size(); k++)
            {vec=v[nod][k].first;
            cost=v[nod][k].second;
                if(d[vec]>d[nod]+cost)
                {
                    d[vec]=d[nod]+cost;
                    if(viz[vec]==0)
                    {q.push(vec); viz[vec]=1;}
                }
            }
    }
}

int main()
{
    int i,j, x,y, ok=1;
    citire();
    bellman();
    for(i=1; i<=n; i++)
       for(j=0; j<v[i].size(); j++)
       {
           x=v[i][j].first;
           y=v[i][j].second;
           if(d[x]>d[i]+y)
           {
               ok=0;
               break;
           }
       }
    if(ok)
        for(i=2; i<=n; i++)
        g<<d[i]<<" ";
       else
        g<<"Ciclu negativ!";

    f.close();
    g.close();
    return 0;
}