#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
typedef pair<int,int> ipair;
int n,m,s,dist[100001];
vector <ipair> v[100001];
int relax[100001];
priority_queue <ipair, vector<ipair> ,greater<ipair>> q;
int main()
{
    f>>n>>m;
    s=1;
    int a,b,d;
    int valmax=1<<30;
    for(int i=1;i<=n;i++)dist[i]=valmax;
    for(int i=1;i<=m;i++){ f>>a>>b>>d;
                           ipair x1;
                           x1.first=d;
                           x1.second=b;
                           v[a].push_back(x1);
                         }
    ipair x;
    x.first=0;
    x.second=s;
    dist[s]=0;
    q.push(x);
    bool ok=1;
    while(q.size() && ok)
    {
      ipair x2=q.top();
      q.pop();
      relax[x2.second]++;
      if(relax[x2.second]==n)
      {
          ok=0;
          dist[dist[x2.second]]=0;
          x2.first=1;
      }
      if(x2.first==dist[x2.second])
      {
        for(int i=0;i<v[x2.second].size();i++)
        {
          if(x2.first+v[x2.second][i].first<dist[v[x2.second][i].second])
          {dist[v[x2.second][i].second]=x2.first+v[x2.second][i].first;
           ipair x3;
           x3.first=dist[v[x2.second][i].second];
           x3.second=v[x2.second][i].second;
           q.push(x3);
          }
        }
      }
    }
   if(ok) for(int i=2;i<=n;i++){if(dist[i]!=valmax)g<<dist[i]<<" ";
                          else g<<-1<<" ";
                          }
     else g<<"Ciclu negativ!";
  g<<'\n';
    return 0;
}