#include <stdio.h>
#include <deque>
using namespace std;
FILE *f,*g;

int n,m;
int start[100002],t[2][700003],c[100002],used[100002],itnod[100002],dist[100002];

deque <int> deq;

struct
{
  int nod, cost;
}vecin;

void read()
{
  fscanf(f,"%d %d",&n,&m);
  int x,y,k=0;
  for(int i=1;i<=m;i++)
  {
    fscanf(f,"%d %d %d",&x,&y,&c[i]);
    t[0][i]=y;
    t[1][i]=start[x];
    start[x]=i;
  }
}

int main()
{
    f=fopen("bellmanford.in","r");
    g=fopen("bellmanford.out","w");
    read();
    for(int i=2;i<=n;i++)
      dist[i]=999999999;
    deq.push_back(1);
    used[1]=1;
    int node,poz;
    while(!deq.empty())
    {
      node=deq.front();
      poz=start[node];
      used[node]=0;
      while(poz)
      {
        vecin.nod=t[0][poz];
        vecin.cost=c[poz];

        if(dist[vecin.nod]>dist[node]+vecin.cost)
        {
          dist[vecin.nod]=dist[node]+vecin.cost;
          if(!used[vecin.nod])
          {
            deq.push_back(vecin.nod);
            used[vecin.nod]=1;
            if(++itnod[vecin.nod] > n)
            {
              fprintf(g,"Ciclu negativ!");
              return 0;
            }
          }
        }

        poz=t[1][poz];
      }
      deq.pop_front();
    }
    for(int i=2;i<=n;i++)
      fprintf(g,"%d ",dist[i]);
    return 0;
}