#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
const int inf=2000000000;
struct element
{
    int y,cost;
}e1;
int n,m,i,x,y,c,viz[50005],d[50005];
bool eq[50005];

vector <element> v[50005];
queue <int> q;

element make_elem(int y, int c)
{
    element e;
    e.y=y;
    e.cost=c;
    return e;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        e1=make_elem(y,c);
        v[x].push_back(e1);
    }
    for (i=2; i<=n; i++)
        d[i]=inf;
    q.push(1);
    eq[1]=1;
    while (!q.empty())
    {
        x=q.front();
        q.pop();
        eq[x]=0;
        for (i=0; i<v[x].size(); i++)
        {
            y=v[x][i].y;
            if (d[y]>d[x]+v[x][i].cost)
            {
                d[y]=d[x]+v[x][i].cost;
                viz[y]++;
                if (viz[y]>n)
                {
                    printf("Ciclu negativ!\n");
                    return 0;
                }
                if (eq[y]==0)
                {
                    q.push(y);
                    eq[y]=1;
                }
            }
        }
    }
    for (i=2; i<=n; i++)
        printf("%d ",d[i]);
    printf("\n");
    return 0;
}