#include <fstream>
#define infinit 9999999

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int d[5000],C[5000][5000],viz[50000],n,m;

bool bellmanford()
{
    int i,j,k;
    for(i=1;i<=n;++i)
        d[i]=C[1][i];
    viz[1]=1;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            for(k=1;k<=n;++k)
                if(C[j][k]!=infinit && d[k]>d[j]+C[j][k])
                    d[k]=d[j]+C[j][k];
    for(j=1;j<=n;++j)
        for(k=1;k<=n;++k)
            if(C[j][k]=infinit && d[k]>d[j]+C[j][k])
                return 0;
    return 1;
}

int main()
{
    int x,y,dist,i;
    f>>n>>m;
    for(i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            C[i][j]=infinit;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>dist;
        C[x][y]=dist;
    }
    if(!bellmanford())
        g<<"Ciclu negativ!";
    else
        for(i=2;i<=n;++i)
            g<<d[i]<<' ';
    return 0;
}