#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in"); ofstream g("bellmanford.out");
int inf=1<<30; 
int n,m,dist[50005],use[50005],acum,y,c,i,x;
struct arc{int nod,cost;};
vector <arc> l[50005];
queue <int> Q;
int main(){
    f>>n>>m;
    while(m--){   f>>x>>y>>c; l[x].push_back((arc){y,c});}
    for(i=2; i<=n; i++) dist[i]=inf;
    Q.push(1); 
    while(!Q.empty()){
		acum=Q.front(); Q.pop();
        use[acum]++;
        if(use[acum]==n) {g<<"Ciclu negativ!\n"; return 0;}
        vector <arc> :: iterator it=l[acum].begin(), sf=l[acum].end();
        for(; it!=sf; ++it){
			if(dist[(*it).nod]>dist[acum]+(*it).cost){
				dist[(*it).nod]=dist[acum]+(*it).cost;
                Q.push((*it).nod);
            }
        }
    }
    for(i=2; i<=n; i++) g<<dist[i]<<" ";
    g<<"\n";  return 0;
}