#include <fstream>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,x,y,c,i,j,d[50001],nr[50001];
bool v[50001];
struct nod{
    int cost;
    int vecin;
    nod *next;
};
struct coada{
    int nodc;
    coada *next;
};


 typedef nod* lista;
 lista q;
 lista l[50001];


int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;

        q=new nod;
        q->cost=c;
        q->next=l[x];
        q->vecin=y;
        l[x]=q;
    }

    d[1]=0;
    for(i=2;i<=n;i++) d[i]=1000000000;

    coada *st, *en, *a;
    st=new coada;
    st->nodc=1;
    en=st;
    st->next=NULL;

    nr[1]=1;
    v[1]=1;

    while(st!=NULL)
    {
        int nod=st->nodc;
        for(q=l[nod];q!=NULL;q=q->next)
        {
            if(d[q->vecin]>q->cost+d[nod])
            {
                d[q->vecin]=q->cost+d[nod];
                if(v[q->vecin]==0) {nr[q->vecin]++; a=new coada; a->next=NULL; a->nodc=q->vecin; en->next=a; en=a;
                v[q->vecin]=1;}
                if(nr[q->vecin]>n-1)
                {
                    fout<<"Ciclu negativ!";
                    return 0;
                }

            }
        }
        v[nod]=0;
        st=st->next;
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";



    return 0;
}