#include <fstream>
#define maxn 50010
#define maxm 250010
#define inf 1000000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct muchie
{
  long a,b,c;
} e[maxm];
long n,m,i,j,k,cost[maxn];
void init()
{ long i;
  cost[1]=0;
  for(i=2;i<=n;i++)
  cost[i]=inf;
}
void bellman ()
{ long i,j;
  for (i=1;i<=n;i++)
  for(j=1;j<=m;j++)
  if(cost[e[j].a]+e[j].c<cost[e[j].b]) cost[e[j].b]=cost[e[j].a]+e[j].c;

}
int ciclunegativ()
{ long i;
  for(i=1;i<=m;i++)
  if(cost[e[i].a]+e[i].c<cost[e[i].b]) return 1;
  return 0;

}
int main()
{ int i;
  f>>n>>m;
  for(i=1;i<=m;i++)
  f>>e[i].a>>e[i].b>>e[i].c;
  init();
  bellman();
  if(ciclunegativ())
  { g<<"ciclu negativ"<<'\n';
    return 0;
  }
  for(i=2;i<=n;i++)
  g<<cost[i]<<" ";
    return 0;
}