#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector <pair <int,int> > v[50001];
int n,m,ap[50001],i,x,y,c,d[50001],j;
bitset <50001> viz;
queue <int> q;
bool cn=false;
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
      f>>x>>y>>c;
      v[x].push_back(make_pair(y,c));
    }
    for (i=1;i<=n;i++)
      d[i]=1000000000;
    d[1]=0,viz[1]=true;
    q.push(1);
    while(!q.empty() && !cn)
    {
      x=q.front();
      q.pop();
      viz[x]=false;
      for (j=0;j<v[x].size();j++)
      if (d[v[x][j].first]>d[x]+v[x][j].second)
        {
          d[v[x][j].first]=d[x]+v[x][j].second;
          if (viz[v[x][j].first]==false)
             if (ap[v[x][j].first]>n)
              cn=true;
          else {
          q.push(v[x][j].first);
          viz[v[x][j].first]=true;
          ap[v[x][j].first]++;
          }
        }
    }
    if (cn==true)
      g<<"Ciclu negativ !";
    else
      for (i=2;i<=n;i++)
      g<<d[i]<<' ';
    return 0;
}