#include <fstream>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,c,k,m,i,vl,x,y,v[50005],d[50005],g[50005];
struct nod{int nd,val;}q;
vector<nod>V[50005];
queue<int>C;
int main()
{fin>>n>>m;
 for(i=1;i<=m;i++)
    {fin>>x>>y>>vl;
     g[x]++;
     q.nd=y;
     q.val=vl;
     V[x].push_back(q);
    }
 C.push(1);
 for(i=1;i<=n;i++)
    d[i]=1000000000;
d[1]=0;
 while(C.size()>0)
      {c=C.front();
       v[c]++;
       C.pop();
       if(v[c]>n){fout<<"Ciclu negativ!";break;}
       else {for(i=0;i<g[c];i++)
                {if(d[c]+V[c][i].val<d[V[c][i].nd])
                   {d[V[c][i].nd]=d[c]+V[c][i].val;
                    C.push(V[c][i].nd);
                   }
                }
            }
      }
 for(i=2;i<=n;i++)
    fout<<d[i]<<" ";
}