#include<bits/stdc++.h>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
typedef pair<pair<int,int>,int>trei;

#define n1 first.first
#define n2 first.second
#define cost second
int inf=1e9;
bool in_q[50001];
vector<vector<pair<int,int>>>muchii(50001,vector<pair<int,int>>(0));
vector<int>distanta(50001,inf);
int n,m;
int main()
{in>>n>>m;
distanta[1]=0;
queue<trei>q;

for(int i=1;i<=m;i++)
{int x,y,z;
in>>x>>y>>z;
muchii[x].push_back({y,z});
  q.push({{x,y},z});
}
for(int k=1;k<=n;k++)
{int ct=q.size();
for(int i=1;i<=ct;i++)
{trei muchie=q.front();
in_q[muchie.n1]=0;
q.pop();
int nod1=muchie.n1,nod2=muchie.n2,cost=muchie.cost;
if(distanta[nod2]>distanta[nod1]+cost)
{distanta[nod2]=distanta[nod1]+cost;
for(auto x:muchii[nod2])
    if(!in_q[x.first])
{q.push({{nod2,x.first},x.second});
in_q[x.first]=1;
}
}
}}
if(q.size())
    out<<"Ciclu negativ!";
else
    for(int i=2;i<=n;i++)out<<distanta[i]<<" ";
}