#include <bits/stdc++.h>
#define INF 1<<30
#define nmax 50001
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,s,x,y,c,d[nmax],m,i,k,min1,l,nod,fr[nmax],ciclu;
vector <pair<int,int> >v[nmax];

queue <int  > q;

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

    for(i =1 ; i <= n ; i ++ )
        d[i]=INF;

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

    }


    d[1]=0;
    fr[1]++;
    q.push(1);


while(!q.empty()&&!ciclu)
    {

        nod=q.front();
        q.pop();


            for(i=0;i<v[nod].size();i++)

        {   x=v[nod][i].first;

            if(d[x]>d[nod]+v[nod][i].second)
            {
                  d[x]=d[nod]+v[nod][i].second;
                  if(fr[x]>n)
                    ciclu=1;
                  else
                  {
                      q.push(x);
                      fr[x]++;
                  }

            }

        }
    }
if(!ciclu)
    for(i=2; i<=n; i++)

            g<<d[i]<<" ";
else
    g<<"Ciclu negativ!";
    return 0;
}