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

#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]=1;

       for(vecin = G[Nod].begin();vecin!=G[Nod].end();vecin++)
       {    n_vecin=(*vecin).varf;
            c_vecin=(*vecin).cost;

           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]=false;
                   cnt[n_vecin]++;
                   if(cnt[n_vecin]>n)
                   {
                       g<<"Ciclu negativ!";
                       return 0;
                   }

               }

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