#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#include <algorithm>
std::ifstream fin ("bellmanford.in");
std::ofstream fout("bellmanford.out");

int n,m;
int dist[50500];
int vis[50500];
bool inpq[50500];
struct nod
{
  int x, d;
};
std::vector<nod> v[50500];
std::priority_queue<int> pq;

int main()
{
  fin>>n>>m;
  for(int i=0;i<m;i++)
  {
    int j,k,o;
    fin>>j>>k>>o;
    v[j].push_back({k,o});
  }
  for(int i=1;i<=n;i++)
    dist[i]=INT_MAX;
  dist[1]=0;
  pq.push(1);
  while(!pq.empty())
  {
    int tp = pq.top();
    pq.pop();
    inpq[tp]=false;
 //   std::cout<<tp.x<<"\n";
    for(int i=0;i<v[tp].size();i++)
    {
      nod elem = v[tp][i];
      if(elem.d+dist[tp]<dist[elem.x])
      {
        if(vis[elem.x]>n) 
        {
          fout<<"Ciclu negativ!";
          return 0;
        }
        dist[elem.x]=elem.d+dist[tp];
        if(!inpq[elem.x])
        {
          pq.push(elem.x);
          inpq[elem.x]=true;
        }
        vis[elem.x]++;
      }
    }
  }
  for(int i=2;i<=n;i++)
    fout<<dist[i]<<" ";//*/
}