#include <fstream>
#include <queue>
#define inf 100000000
using namespace std;
struct nod{int info,c; nod*adr;}*v[50005],*p;
int d[50001],nrq[50001],n,m,i,x,y,c;
queue<int>Q;
bool ok,inq[50001];
int bellman_ford()
{int l,k,nd,c;
    l=1; k=1; d[1]=0;
    Q.push(1);
    for(i=2;i<=n;i++) d[i]=inf;
    while(!Q.empty())
    {
        nd=Q.front();
        Q.pop();
        inq[nd] = false;
        p=v[nd];
        while(p)
        {
            y=p->info;
            c=p->c;
            if(d[nd]+c < d[y])
            {
              d[y] = d[nd]+c;
              if(!inq[y])
              {
                 nrq[y]++;
                 if(nrq[y] == n) return 0;
                 Q.push(y);
              }
            }
            p=p->adr;
        }
    }
    return 1;
}
int main()
{
    ifstream f("bellmanford.in"); ofstream g("bellmanford.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        p=new nod;
        p->info=y; p->c=c; p->adr=v[x]; v[x]=p;
    }
    ok=bellman_ford();
    if(!ok)g<<"Ciclu negativ!";
     else
    for(i=2;i<=n;i++)
     g<<d[i]<<" ";
    f.close();g.close();
  return 0;
}