#include <fstream>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,a[5010][5010],m;
int d[50010];
#define infinit 1010

void citire()
{   f>>n>>m; int x1=0,y1=0; short c1=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;++j) if( i != j ) a[i][j]=infinit;
    while( m )
    {   f>>x1>>y1>>c1; a[x1][y1]=c1;
        m--;
    }
}

void afis()
{   for(int i=1;i<=n;g<<'\n',++i)
        for(int j=1;j<=n;++j) g<<a[i][j]<<" ";
}

int Bellman_Ford(int x)
{   int ok=0;

    for(int i=1;i<=n;++i) d[i]=infinit;
    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] != infinit and a[j][k] != infinit )
                    if( d[k] > d[j] + a[j][k] )
                    {   d[k] = d[j] + a[j][k];
                        ok=1;
                    }
    }

    if( ok == 1 ) return 0;
    return 1;
}

int main()
{   citire();

    if( Bellman_Ford(1) == 0 ) g<<"Ciclu negativ!";
    else for(int i=2;i<=n;++i) g<<d[i]<<" ";

g.close();
return 0;
}