#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int nmax = 5e4 + 4;
int n,m;
int d[nmax],vizitat[nmax];
vector<pair<int,int> > adj[nmax];
int main()
{
fin>>n>>m;
for(;m--;)
{
int x,y,c;
fin>>x>>y>>c;
adj[x].push_back({y,c});
}
for(int i=2; i<=n; i++)
d[i] = INT_MAX;
queue<int> q;
q.push(1);
while(!q.empty())
{
int i = q.front();
q.pop();
vizitat[i] ++;
if(vizitat[i] >= n)
{
fout<<"Ciclu negativ!";
return 0;
}
for(auto p: adj[i])
{
int pi = p.first;
int cost = p.second;
if(d[pi] > d[i] + cost)
{
d[pi] = d[i] + cost;
q.push(pi);
}
}
}
for(int i=2; i<=n; i++)
{
fout<<d[i]<<" ";
}
return 0;
}