#include <fstream>
#define pinf 1<<30
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct nod{
    int info,c;
    nod *next;
            }*l[50001],*p;
int i,j,n,viz[50001],aparitii[50001],m,cost,x,y,co[2500001],pr,u,d[50001];
int bellmanford(int start)
{
    pr=1;
    u=1;
    co[u]=start;
    for(i=1;i<=n;++i)
        {
            d[i]=pinf;
            viz[i]=0;
            aparitii[i]=0;
        }
    d[start]=0;
    viz[start]=1;
    aparitii[start]++;
    while(pr<=u)
    {
        i=co[pr];
        viz[i]=0;
        p=new nod;
        p=l[co[pr++]];
        while(p)
        {
            j=p->info;
            cost=p->c;
            if(d[j]>d[i]+cost)
            {
                d[j]=d[i]+cost;
                if(viz[j]==0)
                {
                    viz[j]=1;
                    if(aparitii[j]>n)
                        return 0;
                    aparitii[j]++;
                    co[++u]=j;
                }
            }

           p=p->next;
        }
    }
    return 1;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
        {
            fin>>x>>y>>cost;
            p=new nod;
            p->info=y;
            p->c=cost;
            p->next=l[x];
            l[x]=p;
        }
    bellmanford(1);
    if(bellmanford(1)==0)
        fout<<"Ciclu negativ!";
    else
        for(i=2;i<=n;++i)
            fout<<d[i]<<" ";

    return 0;
}