#include <cstdio>
#include <vector>
#include <queue>
#define INF 10000000
using namespace std;
struct graf
{
vector <int> nod, cost;
};
graf g[50001];
queue <int> q;
int Cost[50001], nrit[50001];
bool sel[50001], ciclu;
void bellman (int n)
{
int i, x, y; q.push(1); sel[1]=true;
for (i=2; i<=n; i++) Cost[i]=INF;
while (!q.empty())
{
x=q.front(); q.pop();
for (i=0; i<g[x].nod.size(); i++)
{
y=g[x].nod[i];
if (Cost[x]+g[x].cost[i]<Cost[y])
{
Cost[y]=Cost[x]+g[x].cost[i];
if (!sel[y])
{
sel[y]=true;
q.push(y);
nrit[y]++;
if (nrit[y]>n)
{
printf("Ciclu negativ!");
ciclu=true;
return;
}
}
}
}
}
}
int main()
{
int n, m, i, x, y, z;
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&z);
g[x].nod.push_back(y);
g[x].cost.push_back(z);
}
bellman(n);
if (!ciclu)
{
for (i=2; i<=n; i++) printf("%d ",Cost[i]);
}
return 0;
}