#include<stdio.h>
#include<vector>
using namespace std;
#define nmax 50005
#define inf nmax*1000
struct element{int n, c;};
int n, m, i, x, inc;
int dmin[nmax];
bool ok, ex[nmax];
vector <int> co;
element el;
vector <element> ma[nmax];
vector <element> ::iterator it;

void citire()
{
    scanf("%ld %ld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%ld %ld %ld",&x,&el.n,&el.c);
        ma[x].push_back(el);
    }
}


void rezolvare()
{
    for (i=2;i<=n;i++)
        dmin[i]=inf;
    ex[1]=1;
    co.push_back(1);    inc=0;
    while (inc<co.size())
    {
        x=co[inc]; inc++;
        ex[x]=0;
        for (it=ma[x].begin();it!=ma[x].end();it++)
            if (dmin[(*it).n]>dmin[x]+(*it).c)
            {
                dmin[(*it).n]=dmin[x]+(*it).c;
                if (!ex[(*it).n])
                {
                    co.push_back((*it).n);
                    ex[(*it).n]=1;
                }
            }
        if (co.size()>n*m)
            break;
    }
    ok=1;
    for (i=1;((i<=n)&&(ok));i++)
        for (it=ma[i].begin();((it!=ma[i].end())&&(ok));it++)
            if (dmin[(*it).n]>dmin[i]+(*it).c)
                ok=0;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    citire();
    rezolvare();
    if (!ok)
        printf("Ciclu negativ!\n");
    else
        for (i=2;i<=n;i++)
            printf("%ld ",dmin[i]);
    return 0;
}