#include <fstream>
#include <vector>
#define NMAX 50002
#define INF 1000000000
#include <queue>
#include <vector>
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

void citire();
bool bellmanford(); /// 0 daca exista circutie de cost negativ si 1 altfel
void afisare();

queue<int> c;
struct varf {int x, c;};
vector<varf> G[NMAX];///liste de adiacenta cu costuri
int pre[NMAX];
bool uz[NMAX];
int cmin[NMAX];
int sol[NMAX];
int nr[NMAX];
int n, x0=1;
int i, j;
bool rez;
int main()
{
    citire();
    rez=bellmanford();
    if (rez)
        afisare();
        else fout<<"Ciclu negativ!";
    return 0;
}
void citire()
{
    int i, x, y, c, j,m;
    varf aux;
    fin>>n>>m;
    while(fin>>i>>j>>c)
          {
           ///in lista de adiacenta a lui x trebuie sa adaug perechea (j,c)
           aux.x=j; aux.c=c;
           G[i].push_back(aux);
          }
    for (i=1; i<=n; i++) cmin[i]=INF;
    cmin[x0]=0;
}
bool bellmanford()
{int x, vf, cost, i;
    ///initializez coada cu vf de start
    c.push(x0);
    nr[x0]=1;
    while (!c.empty())
          {
           x=c.front(); c.pop();
           ///parcurg lista de adiacenta a lui x
           for (i=0; i<G[x].size(); i++)
               {
                vf=G[x][i].x;
                cost=G[x][i].c;
                if (cmin[vf]>cmin[x]+cost)
                   {
                    cmin[vf]=cmin[x]+cost;
                    c.push(vf);
                    nr[vf]++;
                    if (nr[vf]==n) return 0;
                   }
               }
          }
     return 1;
}

void afisare()
{
  for (i=2; i<=n; i++)
       fout<<cmin[i]<<" ";
}