#include <fstream>
#define  inf 50000001
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,x,y,z,d[22001],c[22001][22001];
bool ok;
void citire()
{
    int i,j;
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j)
                c[i][j]=0;
            else
                c[i][j]=inf;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>z;
        c[x][y]=z;
    }
    for(i=1;i<=n;i++)
        d[i]=c[1][i];
}
void prelucrare()
{
    int i,j,k;
    for(i=1;i<n;i++)
    {
        ok=0;
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
                if((c[j][k]!=inf)&(d[j]!=inf))
                    if(d[k]>c[j][k]+d[j])
                    {
                        d[k]=c[j][k]+d[j];
                        ok=1;
                    }
    }
    if(!ok)
        for(i=2;i<=n;i++)
            g<<d[i]<<" ";
    else
        g<<"Ciclu negativ!";
}
int main()
{
    citire();
    prelucrare();
}