#include <cstdio>
#include <queue>

using namespace std;

struct P
{
    int nod,cost;
    P *urm;
};

queue <int> coada;

P *v[50001];
int dist[50001];
int INF=(1<<31)-1;
int cnt[50001];

void ia_varf(int x)
{
    P *p;
    p=v[x];
    while (p)
    {
        if (dist[x]+p->cost<dist[p->nod])
        {
            dist[p->nod]=dist[x]+p->cost;
            coada.push(p->nod);
        }
        p=p->urm;
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int n,m;
    scanf("%d %d\n",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d %d %d\n",&a,&b,&c);
        if (v[a]==NULL)
        {
            P *p;
            p=new P;
            p->nod=b;
            p->cost=c;
            p->urm=NULL;
            v[a]=p;
        }
        else
        {
            P *p;
            p=new P;
            p->nod=b;
            p->cost=c;
            p->urm=v[a];
            v[a]=p;
        }
    }
    for (int i=2;i<=n;i++)
        dist[i]=INF;
    coada.push(1);
    int oO=1;
    while (!coada.empty())
    {
        cnt[coada.front()]++;
        if (cnt[coada.front()]>=n)
        {
            printf("Ciclu negativ!");
            while (!coada.empty())
                coada.pop();
            coada.push(1);
            oO=2;
        }
        else ia_varf(coada.front());
        coada.pop();
    }
    if (oO==1)
        for (int i=2;i<=n;i++)
            printf("%d ",dist[i]);
}