#include<iostream>
#include<fstream>
#define MAX 1000
using namespace std;

 struct muchie
{
  int src;
  int dest;
  int cost;
};
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
void bellman_ford(int n,muchie e[],int src_graph,int m)
{
  int u,v,cost,i,j=0;
  int dis[MAX];

  /* initializing array 'dis' with 999. 999 denotes infinite distance */
  for(i=1;i<=n;i++)
  {
    dis[i]=999;
  }

  /* distance of source vertex from source vertex is o */
  dis[src_graph]=0;

  /* relaxing all the muchies nv - 1 times */
  for(i=1;i<=n-1;i++)
  {
    for(j=1;j<=m;j++)
    {
      u=e[j].src;
      v=e[j].dest;
      cost=e[j].cost;


      if(dis[u]!=999 && dis[u]+cost < dis[v])
      {
        dis[v]=dis[u]+cost;
      }
    }

  }

  /* checking if negative cycle is present */
  for(j=1;j<=m;j++)
  {
    u=e[j].src;
    v=e[j].dest;
   cost=e[j].cost;

    if(dis[u]+cost < dis[v])
    {
      cout<<"\n\nNEGATIVE CYCLE PRESENT..!!\n";
      return;
    }
  }

  for(i=2;i<=n;i++)
  {
    g<<dis[i]<<" ";
  }

}


int main()
{
  int n,m,src_graph;
  muchie e[MAX];
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

  f>>n>>m;

  src_graph=1;

  for(int i=1;i<=m;i++)
  {
    f>>e[i].src>>e[i].dest>>e[i].cost;
  }

  bellman_ford(n,e,src_graph,m);

  return 0;
}