#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int main(){ifstream f("bellmanford.in");ofstream g("bellmanford.out");int n,m;f>>n>>m;vector<vector<pair<int,int>>>a(n+1);for(int i=0;i<m;++i){int x,y,c;f>>x>>y>>c;a[x].push_back({y,c});}vector<int>d(n+1,1e9),k(n+1,0);vector<bool>iq(n+1,0);queue<int>q;d[1]=0;q.push(1);iq[1]=1;bool ng=0;while(!q.empty()&&!ng){int u=q.front();q.pop();iq[u]=0;for(auto&e:a[u]){int v=e.first,w=e.second;if(d[v]>d[u]+w){d[v]=d[u]+w;if(!iq[v]){q.push(v);iq[v]=1;k[v]++;if(k[v]>n){ng=1;break;}}}}}if(ng)g<<"Ciclu negativ!";else{g<<d[2];for(int i=3;i<=n;++i)g<<" "<<d[i];}}