#include <fstream>
#include <functional>
#include <queue>
#define nmax 400001
#define inf 100000000

using namespace std;


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


class graph{
private:
	vector<pair<int,int>> edges[nmax];
	int nodes;
public:
	graph(int n){
		nodes=n;
	}
	void addedge(int x, int y, int cost){
		edges[x].push_back({y,cost});
	}
	void bellmanford(int source){
		vector<int> dist(nodes+1,inf);
		queue<int> coada;
		int i, nod;
		vector<bool> incoada(nodes+1,0);
		vector<int> viz(nodes,0);
		dist[source]=0;
		coada.push(source);
		while(!coada.empty()){
			nod=coada.front();
			coada.pop();
			incoada[nod]=0;
			++viz[nod];
				if(viz[nod]==nodes){
					g<<"Ciclu negativ!"<<"\n";
					return;
				}
			for(i=0;i<edges[nod].size();i++){
				if(dist[nod]+edges[nod][i].second<dist[edges[nod][i].first]){				
					dist[edges[nod][i].first]=dist[nod]+edges[nod][i].second;
				 if(!incoada[edges[nod][i].first]){
				 	incoada[edges[nod][i].first]=1; 	
				     coada.push(edges[nod][i].first);
				 }
				}
			}
		}
		for(i=2;i<=nodes;i++)
			g<<dist[i]<<" ";
		g<<"\n";
	}

};
int main(){
  int n, m, i, x, y, cost;
  ios::sync_with_stdio(false);
  f>>n>>m;
  graph graf(n);
  for(i=1;i<=m;i++){
  	f>>x>>y>>cost;
  		graf.addedge(x,y,cost);
  }
  graf.bellmanford(1);
}