#include <fstream>
#include <vector>
#include <queue>
#define DMAX 50005
#define INF 1000000000

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,start=1;
void citire();
bool bellman();
struct varf{int x;int c;};
vector <varf> LA[DMAX];
queue <int> Q;
int cmin[DMAX]; ///cmin[x]=costul minim al drumului de cost minim de la start la x
int nr[DMAX];   ///nr[x]=de cate ori a fost actualizat un drum de cost minim de la start la x

int main()
{int i;
    citire();
    if(bellman()==0)
       fout<<"Ciclu negativ!"<<'\n';
       else
       for(i=2;i<=n;i++)
           if(cmin[i]==INF) fout<<-1<<' ';
              else
              fout<<cmin[i]<<' ';
    fout<<'\n';
    fout.close();
    return 0;
}
void citire()
{int i,j,x,y,cost;
 varf aux;
 fin>>n>>m;
   for(i=1;i<=m;i++)
       {
        fin>>x>>y>>cost;
        aux.x=y;
        aux.c=cost;
        LA[x].push_back(aux);
       }
}
bool bellman()
//returnam 0 daca nu exista solutie si 1 daca exista solutie
{int i,j;
   for(i=1;i<=n;i++)
       cmin[i]=INF;
   cmin[start]=0;
   Q.push(start);
   while(!Q.empty())
        { j=Q.front();
          Q.pop();
          ///parcurg lista de adiacenta a lui x
          for(i=0;i<LA[j].size();i++)
            if(cmin[LA[j][i].x]>cmin[j]+LA[j][i].c)
               {
                cmin[LA[j][i].x]=cmin[j]+LA[j][i].c;
                nr[LA[j][i].x]++;
                if(nr[LA[j][i].x]==n) return 0;
                Q.push(LA[j][i].x);
               }
        }
   return 1;
}