#include <cstdio>

const int inf=1<<29;
int n,m;
int mat[5000][5000],d[5000];

void bellmanford(int start)
{
    int i,j;
    d[start]=0;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
            if (d[j]>d[i]+mat[i][j])
                d[j]=d[i]+mat[i][j];
    }

}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int i,j,x,y,cost;
    scanf("%d %d",&n,&m);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            mat[i][j]=inf;
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&cost);
        mat[x][y]=cost;
    }
    int start=1;
    for (i=1; i<=n; i++)
        d[i]=inf;
    for (i=1; i<=n-1; i++)
        bellmanford(start);
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
            if (d[j]>d[i]+mat[i][j])
            {
                printf("Ciclu negativ!");
                return 0;
            }
    }
    for (i=2; i<=n; i++)
        printf("%d ",d[i]);
    return 0;
}