#include <fstream>
#include <set>
#include <vector>
#include <iostream>
#define INF 0x3f3f3f3f
#define MAXN 50100
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector < pair <int,int > > g[MAXN];
set <int> s1,s2;
int n,d[MAXN];

void bellman()
{
     bool ok;
     int x,y;
     for(int i=2; i<=n; i++) d[i]=INF;
     d[1]=0;
     s1.insert(1);
     for(int p=1; p<=n; p++)
     {
             ok=0;
             while(s1.size()>0)
             {
                               x=*s1.begin();
                               s1.erase(s1.begin());
                               for(int i=0 ; i<g[x].size(); i++)
                               {
                                       y=g[x][i].first;
                                       if (d[y] > d[x]+g[x][i].second)
                                       {
                                                   d[y]=d[x]+g[x][i].second;
                                                   s2.insert(y);
                                                   ok=1;
                                       }
                               }
             }
             swap(s1,s2);
     }
     if(ok) fout<<"Ciclu negativ!"<<endl;
     else
     for(int i=2; i<=n; i++) fout<<d[i]<<" ";
}

int main()
{
    int m,x,y,c;
    fin>>n>>m;
    while(m--)
    {
             fin>>x>>y>>c;
             g[x].push_back(make_pair(y,c));
    }
    bellman();
    return 0;
}