#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
using namespace std;

#define ll long long 
#define ull unsigned long long
#define INF 1000000

/*------------------------------------------------------------------*/
 
ifstream f{ "dijkstra.in" };
ofstream q{ "dijkstra.out" };

vector<pair<int,int>> graph[50005];
int dist[50005];
int n, m;

bool belmanford(int src)
{
   for(int i = 1; i <=n; ++i)
   {
      dist[i] = INF;
   }
   
   dist[src] = 0;
   queue<int> coada;

   coada.push(src);
   int curent;
   int y;
   int w;

   while(!coada.empty())
   {
      curent = coada.front(); coada.pop();

      for(size_t i = 0; i < graph[curent].size(); ++i)
      {
         y = graph[curent][i].first;
         w = graph[curent][i].second;

         if(dist[curent] + w < dist[y])
         {
            dist[y] = dist[curent] + w;
            coada.push(y);
         }
      }
   }

   return true;
}

int main()
{
   ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

   int x, y, c;
   f >> n >> m;
   for(int i = 0; i < m; ++i)
   {
      f >> x >> y >> c;
      graph[x].push_back(make_pair(y, c));
   }
   if (!belmanford(1)) q << "Ciclu negativ!\n";
   else
   {
      for (int i = 2; i <= n; ++i)
      {
         if (dist[i] == INF) dist[i] = 0;
         q << dist[i] << " ";
      }
   }
   f.close();
   q.close();
   return 0;
}