#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define inf 20001
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
vector<vector<pair<int,int>>> gf(50005);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
int n, m, x, y, c;
int d[50005];
int inq[50005];
bool viz[50005];
void bellmanford(int nodstart)
{
for(int i=1; i<=n; i++)
d[i]=inf;
d[nodstart]=0;
pq.push({1,0});
viz[nodstart]=true;
inq[nodstart]=1;
while(!pq.empty())
{
int nod = pq.top().first;
viz[nod]=0;
pq.pop();
for(auto nodcrt : gf[nod])
{
int vecin = nodcrt.first;
int cost = nodcrt.second;
if(d[vecin] > d[nod] + cost)
{
d[vecin] = d[nod] + cost;
if(!viz[vecin])
{
inq[vecin]++;
if(inq[vecin]>n)
{
cout<<"Ciclu negativ!";
exit(0);
}
pq.push({vecin,d[vecin]});
viz[vecin]=true;
}
}
}
}
for(int i=1; i<=n; i++)
if(d[i])
cout<<d[i]<<' ';
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
while(m--)
{
cin>>x>>y>>c;
gf[x].push_back({y,c});
}
bellmanford(1);
return 0;
}