#include <iostream>
#include <fstream>
#include <queue>
#define INF 1000000
#define NMAX 50000
#define MMAX 250000

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

vector<pair<int,int>> graph[NMAX+1];
int cost[NMAX+1],inQueue[NMAX+1],relaxed[NMAX+1];

int n,m;
int main()
{
		fin >> n >> m;
    for(int i=1;i<=m;i++)
		{
				int x,y,c;
				fin >> x >> y >> c;
				graph[x].push_back({y,c});
		}
    cost[1]=0;
    for(int i=2;i<=n;i++)
		{
			cost[i]=INF;
		}
		queue<int> Q;
		Q.push(1);
    inQueue[1]=1;
    bool ok=1;
    while(!Q.empty() && ok)
		{
			int from = Q.front();
			Q.pop();
      inQueue[from]=0;
      for(auto i : graph[from])
			{
					int to = i.first,c=i.second;
        	if(cost[to] > cost[from] + c && relaxed[to] < n)
					{
            cost[to] = cost[from] + c;
            relaxed[to]++;
            if(relaxed[to]==n)
						{
              ok=0;
						}
						if(!inQueue[to])
						{
							inQueue[to]=1;
              Q.push(to);
						}
					}
			}
		}
		if(!ok)
		{
			fout << "Ciclu negativ!";
		}
		else
		{
			for(int i=2;i<=n;i++)
			{
					fout << cost[i] << " ";
			}
		}
    return 0;
}