#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];
struct nod
{
  int x, d;
};
struct Comp: std::binary_function<nod,nod,bool>
{
  bool operator()(nod n1, nod n2)
  {
    return n1.d<n2.d;
  }
};
std::vector<nod> v[50500];
std::priority_queue<nod,std::vector<nod>,Comp> 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,dist[1]});
  while(!pq.empty())
  {
    nod tp = pq.top();
    pq.pop();
    if(vis[tp.x]>m-1) 
    {
      fout<<"Ciclu negativ!";
      return 0;
    }
    vis[tp.x]++;
 //   std::cout<<tp.x<<"\n";
    for(int i=0;i<v[tp.x].size();i++)
    {
      nod elem = v[tp.x][i];
      if(elem.d+tp.d<dist[elem.x])
      {
        dist[elem.x]=elem.d+tp.d;
        pq.push({elem.x,dist[elem.x]});
      }
    }
  }
  for(int i=2;i<=n;i++)
    fout<<dist[i]<<" ";//*/
}