#include <iostream>
#include <fstream>

#define dim 50005

using namespace std;

const unsigned int inf=2000000000;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

struct elem
{
    int val;
    elem* next;
};

struct graf
{
    int nod,len;
    graf* next;
}*a[dim];

int n,m,d[dim],nrvizitariC[dim];
bool inC[dim];

int main()
{
    fin>>n>>m;
    for (int i=0; i<m; i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        graf* nou=new graf;
        nou->len=cost;
        nou->nod=y;
        nou->next=a[x];
        a[x]=nou;
    }
    d[1]=0;
    for (int i=2; i<=n; i++)
    {
        d[i]=inf;
        inC[i]=false;
    }
    elem *st,*dr;
    st=new elem;
    st->val=1;
    st->next=NULL;
    dr=st;
    inC[1]=true;
    nrvizitariC[1]++;
    while (st!=NULL)
    {
        int nod=st->val;
        inC[nod]=false;
        graf* k=a[nod];
        while (k!=NULL)
        {
            if (d[nod]+k->len<d[k->nod])
            {
                d[k->nod]=d[nod]+k->len;
                if (inC[k->nod]==false)
                {
                    if (nrvizitariC[k->nod]>=n)
                    {
                        fout<<"Ciclu negativ!\n";
                        return 0;
                    }
                    else
                    {
                        elem* nou=new elem;
                        nou->val=k->nod;
                        nou->next=NULL;
                        dr->next=nou;
                        dr=nou;
                        inC[k->nod]=true;
                        nrvizitariC[k->nod]++;
                    }
                }
            }
            k=k->next;
        }
        st=st->next;
    }
    for (int i=2; i<=n; i++)
        fout<<d[i]<<' ';
    return 0;
}