#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INF 1<<30
#define MX 50005
#define nod  (*it).F
#define cost (*it).S
using namespace std;
vector < pair <int,int> > G[MX];
queue <int> q;
vector < pair <int,int> > :: iterator it;
bool u[MX],negativ=false;
int fr[MX];
int dist[MX];
int x,y,m,n,cst;
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
   for(int w=1;w<=n;w++)
   {
       dist[w]=INF;
   }
    while(m--)
    {
        scanf("%d %d %d",&x,&y,&cst);
        G[x].PB(MP(y,cst));
    }
int w;
    dist[1]=0;
   q.push(1);
   while(!q.empty() && !negativ)
   {
      w=q.front();

      for(it=G[w].begin(); it!=G[w].end();it++)
      {
         if(dist[nod]>dist[w]+cost) dist[nod]=dist[w]+cost;
         if(!u[nod])
         {
             q.push(nod);
             fr[nod]++;
             if(fr[nod]>n)
             {
                 printf("Ciclu negativ!");
                 return 0;
             }
             u[nod]=true;
         }
      }
      u[w]=false;
      q.pop();


    }
    int i;
    for(i=2;i<=n;i++)
    {
        printf("%d ",dist[i]);
    }

    return 0;
}