#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct nod{int inf,c;
            nod *leg;}*li[50001],*p;
int i,j,n,k,m,start,c=30000,x,y,cost;
int d[250001];
int minimizeaza()
{
    int ok,j;
    ok=false;
    for(j=1;j<=n;++j)
        {
            p=new nod;
            p=li[j];
            while(p!=NULL)
            {
                if(d[p->inf]>d[j]+p->c)
                    {
                        ok=true;
                        d[p->inf]=d[j]+p->c;
                    }
                p=p->leg;
            }
        }
    return ok;
}
void bellman_ford()
{
    int ok,i;
    for(i=1;i<=n;++i)
            d[i]=c;
    d[start]=0;
    for(i=1;i<n;++i)
        ok=minimizeaza();
    ok=minimizeaza();
    if(ok)
    {
        fout<<"Ciclu negativ!";
        exit(0);
    }

}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>cost;
        p=new nod;
        p->leg=li[x];
        p->inf=y;
        p->c=cost;
        li[x]=p;
    }
    start=1;
    bellman_ford();
    for(i=1;i<=n;++i)
        if(i!=start)
            fout<<d[i]<<" ";
    return 0;
}