#include <fstream>
#include <iostream>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct el{int nod; short cost; int urm;};
el a[250001];
int n,m,cost[50001],inf=1000000000,i,j,x,y, l[50001],k=1,c,poz,mini,p,ok,nd;
bool viz[50001];
void ad(int x,int y,int c)
{
    k++;
    a[k].nod=y;
    a[k].cost=c;
    a[k].urm=l[x];
    l[x]=k;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
            cost[i]=inf;
    }
    cost[1]=0;
    viz[1]=1;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        if(x==1)
            cost[y]=c;
        ad(y,x,c);
    }
    for(k=1;k<n;k++)
    for(i=1;i<=n;i++)
    {

       poz=l[i];
       while(poz)
       {
           nd=a[poz].nod;
           if(cost[i]>cost[nd]+a[poz].cost)
           {
               cost[i]=cost[nd]+a[poz].cost;
               ok=1;
           }
           poz=a[poz].urm;
       }


    }
    for(i=1;i<=n;i++)
    {
        ok=0;

       poz=l[i];
       while(poz)
       {
           nd=a[poz].nod;
           if(cost[i]>cost[nd]+a[poz].cost)
           {
               cost[i]=cost[nd]+a[poz].cost;
               ok=1;
               poz=0;
               i=n+1;
           }
           poz=a[poz].urm;
       }
    }
    if(ok==0)
    {for(i=2;i<=n;i++)
        if(cost[i]==inf)
        g<<0<<" ";
    else
        g<<cost[i]<<" ";}
        else
            g<<"Ciclu negativ!";
    return 0;
}