#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;


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

const int DIM = 250005;
const int oo = (1 << 31) - 1;

vector < pair < int, int> > v[DIM];

int d[DIM];

int n,m;

priority_queue <int, vector <int> > c;

bool viz[DIM];

void bellmanford(int &k)
{

        for(int j = 1;j <= n;j++)
        for(int i = 0;i < v[j].size() ;i++)
        {
            int cost = v[j][i].second;
            int vec = v[j][i].first;

            if(d[j] + cost < d[vec])
            {
                k++;
                d[vec] = d[j] + cost;

            }
        }
    }

int main()
{

   in >> n >> m;

   for(int i = 1; i <= m; i++)
   {
        int x, y, c;

        in >> x >> y >> c;

        v[x].push_back(make_pair(y,c));
   }

   for(int i = 1;i <= n; i++)
    d[i] = oo;

    d[1] = 0;
   for(int i = 1;i <= n - 1;i++)
   {
       int k = 0;
       bellmanford(k);
       if(k == 0)
       {
           for(int j = 2;j <= n;j++)
            out << d[j] <<" ";
           return 0;
       }
       if(k != 0 && i == n - 1)
       {
           int k = 0;
           bellmanford(k);
           if(k!=0)
            out << "Ciclu negativ!";
           else
              {
           for(int j = 2;j <= n;j++)
            out << d[j] <<" ";
            return 0;
                }
       }
   }

      return 0;
}