#include <fstream>
#define nmax 50005
#define mmax 250005
#define inf  250005000
using namespace std;
fstream f1("bellmanford.in", ios::in);
fstream f2("bellmanford.out", ios::out);
long int n, m, cap[nmax], aux[nmax], viz[nmax], nrit[nmax], dist[nmax], coada[nmax], prim, ultim, k, ok;
struct lista
{
   long int val, c;
}  v[mmax];
struct muchii
{
    long int x, y, c;
}muc[mmax];
void citire()
{
    long int i;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>muc[i].x>>muc[i].y>>muc[i].c;
        aux[muc[i].x]++;
    }
    cap[1]=1;
    for(i=2; i<=n+1; i++)
    {
        cap[i]=cap[i-1]+aux[i-1];
        aux[i-1]=cap[i-1];
    }
    for(i=1; i<=m; i++)
    {
        v[aux[muc[i].x]].val=muc[i].y;
        v[aux[muc[i].x]].c=muc[i].c;
        aux[muc[i].x]++;
    }
}
void bellam()
{
   long int nod, i, vec, cost;
   while((k!=0)&&ok)
   {
       nod=coada[prim];
       prim++;
       if(prim>n) prim=1;
       k--;
       viz[nod]=0;
       for(i=cap[nod]; (i<cap[nod+1])&&ok; i++)
       {
           vec=v[i].val;
           cost=v[i].c;
           if(dist[vec]> dist[nod]+cost)
           {
               dist[vec]= dist[nod]+cost;

               if(!viz[vec])
               {
                   viz[vec]=1;
                   ultim++;
                   if(ultim>n) ultim=1;
                   k++;
                   coada[ultim]=vec;
                   nrit[vec]++;
                   if(nrit[vec]>n) ok=0;
               }
           }
       }
   }
}
void init()
{
    long int i;
    ok=1;
    viz[1]=1;
    for(i=2; i<=n; i++)
        dist[i]=inf;
    /*for(i=cap[1]; i<cap[2]; i++)
        dist[v[i].val]=v[i].c;*/
    prim=1;
    ultim=1;
    k=1;
    coada[ultim]=1;
}
void afisare()
{
    if(!ok) f2<<"Ciclu negativ!";
    else
        for(long int i=2; i<=n; i++) f2<<dist[i]<<' ';
}
int main()
{
    citire();
    init();
    bellam();
    afisare();
    return 0;
}