#include<iostream>
#include<fstream>
#include<cstdlib>
#include<queue>
#define infinit 10000000

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");


int n,m,cost[50005],cnt;
bool viz[50005];
vector <int> L[250005];

void Citire()
{
  int x,y,costt;
  fin >> n >> m;
  for (int i=1; i<=m; i++)
   {
      fin >> x >> y >> costt;
      L[x].push_back(y);
	  L[x].push_back(costt);
   }
}

void Lee_Bellman_Ford_BFS_Dijkstra()
{
  queue <int> q;
  int i,j,k,costt;
  q.push(1); // in coada stau noduri
  viz[1]=1;
  
  while (!q.empty())
 {
   k = q.front();
   q.pop();
   if (viz[k] >= n)
   {
   	   fout << "Ciclu negativ\n";
   	   exit(0);
   }
   for (j=0; j<L[k].size(); j=j+2)
       {
            i = L[k][j]; costt = L[k][j+1];
            
            if (viz[i]==0 || cost[i] >= cost[k] + costt)
               {
                   cost[i] = cost[k] + costt;
                   q.push(i);
                   viz[i]++;
               }
       }
 }  
}

void Print_that()
{
 for (int i=2; i<=n; i++)
   fout << cost[i] << " ";
 fout << "\n";
}

int main ()
{
 Citire();
 Lee_Bellman_Ford_BFS_Dijkstra();
 Print_that();
 fin.close();
 fout.close();
 return 0;
}