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

int main()
{   f>>n>>m; short a[n+1][n+1]; 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; else a[i][j]=0;

    while( m )
    {   f>>x1>>y1>>c1; a[x1][y1]=c1;
        m--;
    }

    ///Bellman_Ford

    int ok=0;

    for(int i=1;i<=n;++i) d[i]=infinit;
    d[1]=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;
                    }
    }

    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] )
                    {   g<<"Ciclu negativ!";
                        return 0;
                    }

    for(int i=2;i<=n;++i) g<<d[i]<<" ";

g.close();
return 0;
}