/*
  Bellman-Ford
*/

#include <iostream>
#define inf 1000000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct muchie
{
long u,v,w;       
}E[250005];
long cost[50010];
int main()
{
f>>n>>m;
for(i=1; i<=m; i++)
   f>>e[i].u>>e[i].v>>e[i].w);

cost[1]=0;
  for(i=2; i<=n; i++)
     cost[i]=inf;

for(i=1;i<=n-1;i++)
  for(j=1; j<=m; j++)
    if(cost[e[j].u]+e[j].w<cost[e[j].v])
      cost[e[j].v]=cost[e[j].u]+e[j].w;

cycle=0;
for(j=1; j<=m; j++)
    if(cost[e[j].u]+e[j].w<cost[e[j].v])
       cycle=1;
       
if(cycle)
    {
        g<<"Ciclu negativ!\n";
        return 0;
    }
    for(i=2; i<=n; i++)
        g<<cost[i]<<" ";
return 0;
}