#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#include <queue>
#define inf=INT_MAX
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector < pair <int, int> > L[50001];
queue <int> Q;
int D[50001], S[50001], n, m, Viz[50001], CNT[50001];
void Citire()
{int i, x, y , c;
    f>>n>>m;
 for(i=1;i<=m;i++)
 {f>>x>>y>>c;
     L[x].push_back(make_pair(y,c));
 }
}

void Bellman_Ford(int start)
{ int i, y, c, j;
   int neg_cycle = false;
   for(i=1;i<=n;i++)
        D[i]=INT_MAX;
   D[start] = 0, Q.push(start);
   // in_queue[1].flip();
   while (!Q.empty() && neg_cycle==false)
   {
        int x = Q.front();Q.pop();

        Viz[x] = false;
        for (j = 0; j<L[x].size(); j++)
          if (D[x] < INT_MAX)
          {
             y= L[x][j].first;
             c= L[x][j].second;
              if (D[y] > D[x] + c) {
                D[y] > D[x] + c;
                if (Viz [y]==0) {
                    if (CNT[y] > n )
                        neg_cycle = true;
                    else {
                        Q.push(y);
                        Viz[y] = true;
                        CNT[y] ++;
                    }
                }
            }
          }

   }

    if (!neg_cycle) {
        for (int i = 1; i <= n; ++ i)
            if(i!=start)
                g<< D[i] << " ";
    }
    else
        g << "Ciclu negativ!\n";
    g.close();
}




int main()
{
Citire();
int start=1;
Bellman_Ford(start);

f.close();
g.close();
    return 0;
}