#include <iostream>
#include <fstream>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct nod
{
    nod* urm;
    int inf,cost;
};
nod* v[50001];
int cost[50001],n,m,i;

int main()
{
    int inf=9999999,ok=0;
    f>>n>>m;
    int x,y,z;
for(i=1;i<=m;i++)
{
    f>>x>>y>>z;
    if(v[x]!=NULL)
    {
    nod* q=new nod;
    q->inf=y;
    q->cost=z;
    q->urm=v[x]->urm;
    v[x]->urm=q;
    }
    else
    {
    nod* q=new nod;
    q->inf=y;
    q->cost=z;
    q->urm=NULL;
    v[x]=q;
    }
}
for(i=1;i<=n;i++)
    cost[i]=inf;
cost[1]=0;
for(i=1;i<=n;i++)
{
    if(v[i])
    {
        nod* p=v[i];
        while(p)
        {
            if(cost[p->inf]>cost[i]+p->cost)
                cost[p->inf]=cost[i]+p->cost;
                p=p->urm;
        }
    }
}
for(i=1;i<=n;i++)
{
    if(v[i])
    {
        nod* p=v[i];
        while(p)
        {
            if(cost[p->inf]>cost[i]+p->cost)
                {
                    ok=1;
                    g<<"Ciclu negativ!";
                    p->urm=NULL;
                }
                p=p->urm;
        }
    }
}
if(ok==0)
for(i=2;i<=n;i++)
    g<<cost[i]<<" ";
    return 0;
}