#include <iostream>
#include <fstream>

#define dim 50005

using namespace std;

const unsigned int inf=2000000000;

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

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

int n,m,d[dim],coada[dim*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;
    }
    int st=0,dr=0;
    coada[st]=1;
    inC[1]=true;
    nrvizitariC[1]++;
    while (st<=dr)
    {
        while (coada[st]==-1)
            st++;
        if (st>dr)
            break;
        int nod=coada[st++];
        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
                    {
                        coada[++dr]=k->nod;
                        inC[k->nod]=true;
                        nrvizitariC[k->nod]++;
                    }
                }
            }
            /*else if (pozinC[k->nod]!=-1)
            {
                coada[pozinC[k->nod]]=-1;
                pozinC[k->nod]=-1;
            }*/
            k=k->next;
        }
    }
    for (int i=2; i<=n; i++)
        fout<<d[i]<<' ';
    return 0;
}