#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;int N,M,C[50100],B[50100];queue<int>Q;vector<pair<int,int>>V[50100];int main(){ifstream w("bellmanford.in");ofstream o("bellmanford.out");w>>N>>M;for(int x,y,c;M--;){w>>x>>y>>c;V[x].push_back({y,c});}for(int i=2;i<=N;i++)C[i]=(1<<30);Q.push(1);while(!Q.empty()){int x=Q.front();Q.pop();B[x]++;if(B[x]>=N)return o<<"Ciclu negativ!",0;for(auto y:V[x])if(C[y.F]>C[x]+y.S)C[y.F]=C[x]+y.S,Q.push(y.F);}for(int i=2;i<=N;i++)o<<C[i]<<' ';}