#include <fstream>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct nod
{
    int val,cost;
    nod *urm;
};
struct coada
{
    int val;
    coada *prec,*urm;
};
typedef coada *pcoada;
typedef nod *pnod;
#define nmax 50003
#define inf 2000000000
pnod v[nmax],p;
pcoada first,last,umblu,q;
void ad(int x,int y,int c)
{
    p=new nod;
    p->val=y;
    p->cost=c;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
int dist[nmax],cnt[nmax];
bool use[nmax];
void elimin()
{
    if(first==last)
        first=last=umblu=0;
    else
    {
        if(umblu==first)
        {
            first=first->urm;
            first->prec=0;
            delete umblu;
            umblu=first;
        }
        else
            if(umblu==last)
            {
                last=last->prec;
                last->urm=0;
                delete umblu;
                umblu=last;
            }
            else
            {
                umblu->urm->prec=umblu->prec;
                umblu->prec->urm=umblu->urm;
                q=umblu;
                umblu=umblu->urm;
                delete q;
            }
    }
}
int main()
{
    int n,m,i,ok=1,x,y,c;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
        dist[i]=inf;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ad(x,y,c);
    }
    dist[1]=0;
    first=new coada;
    first->urm=first->prec=0;
    first->val=1;
    last=first;
    use[1]=1;
    int bun;
    while(first and ok)
    {
        umblu=first;
        while(umblu)
        {
            p=v[umblu->val]->urm;
            bun=0;
            while(p)
            {
                if(dist[p->val]>dist[umblu->val]+p->cost)
                {
                    bun=1;
                    dist[p->val]=dist[umblu->val]+p->cost;
                    cnt[p->val]+=1;
                    if(cnt[p->val]>=n)
                        ok=0;
                    if(use[p->val]==0)
                    {
                        q=new coada;
                        q->val=p->val;
                        q->prec=last;
                        q->urm=0;
                        last->urm=q;
                        last=q;
                    }
                }
                p=p->urm;
            }
            if(bun==0)
                elimin();
            else
                umblu=umblu->urm;

        }
    }
    if(ok==0)
        g<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
            g<<dist[i]<<" ";
    return 0;
}