#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
#define inf 1000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int a[5000][5000], m, n, x, y, c, d[50002];
void citire(){
f>>n>>m;
for(int i=0; i<m; ++i){
    f>>x>>y>>c;
    a[x][y]=c;
    }
for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
    if(!a[i][j]) a[i][j]=inf;
}

int bf(int x)
{
int ok;
d[x] = 0;
   for (int i=1; i<=n; i++){
        ok=0;
	   for (int j=1;j<=n;j++)
         for (int k=1;k<=n;k++)
            if(d[j]!=inf&&a[j][k]!=inf)
               if (d[k]>d[j]+a[j][k])
			   {
                  d[k] = d[j]+a[j][k];
                ok=1;
			}
   }
   if(ok==1) g<<"Ciclu negativ!";
   return ok;
}

int main()
{
    citire();
    for(int i=0; i<=n; ++i)
        d[i]=inf;
    if(!bf(1))
        for(int i=1; i<=n; ++i)
            if(i!=1) g<<d[i]<<' ';
    g.close();
    return 0;
}