#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector < pair<int, int> > g[50001];
queue <int> q;

int n, m, x, y, c, d[50001], in[50001], viz[50001];
int inf=1000000000;
int bellmanford(int s)
{int i, j, nod, vecin, cost;
for(i=1; i<=n; i++)
{d[i]=inf;
in[i]=viz[i]=0;
}
d[s]=0;
in[s]=1;
q.push(s);
while(!q.empty())
{
nod=q.front();
viz[nod]++;
if(viz[nod]>=n) return 0;
in[nod]=0;
q.pop();
for(i=0; i<g[nod].size(); i++)
{vecin=g[nod][i].first;
cost=g[nod][i].second;
if(d[vecin]>d[nod]+cost)
{d[vecin]=d[nod]+cost;
if(in[vecin]==0)
{q.push(vecin);
in[vecin]=1;
}
}
}
}
return 1;
}

int main()
{int i;
fin>>n>>m;
for(i=1; i<=m; i++)
{fin>>x>>y>>c;
g[x].push_back(make_pair(y, c));
}

if(bellmanford(1)==1)
{for(i=2; i<=n; i++)
fout<<d[i]<<' ';
}
else fout<<"Ciclu negativ!";

    return 0;
}