#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define INF   0x3f3f3f3f
#define Nmax  250005

#define cost second
#define varf first
using namespace std;
fstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,i,j,x,y,c,cnt[Nmax],Nod;
int n_vecin,c_vecin;
long long D[Nmax];
bool pus[Nmax];
vector <pair<int,int>> G[Nmax];
vector <pair<int,int>> :: iterator vecin;
queue <int> q;

int main()
{
   f>>n>>m;
   for(i=1;i<=m;i++)
   {
       f>>x>>y>>c;
       G[x].pb(mp(y,c));
   }

   memset(D,INF,sizeof(D));
   memset(pus,false,sizeof(pus));
   memset(cnt,0,sizeof(cnt));
   D[1]=0;pus[1]=true;q.push(1);
   while(!q.empty())
   {
       Nod=q.front();q.pop();pus[Nod]=false;
        for(auto it:G[Nod])
        {
            n_vecin=it.varf;
            c_vecin=(*vecin);

            if(D[n_vecin]>D[Nod]+c_vecin)
            {
               D[n_vecin]=D[Nod]+c_vecin;
               if(!pus[n_vecin])
               {
                   q.push(n_vecin);
                   pus[n_vecin]=true;
                   cnt[n_vecin]++;
                   if(cnt[n_vecin]>n)
                   {
                       g<<"Ciclu negativ!";
                       return 0;
                   }

               }
            }


   }
   for(i=2;i<=n;i++)g<<D[i]<<' ';
    return 0;
}