#include <fstream>
#include <queue>
#define inf 100000000
using namespace std;
struct nod{int info,c; nod*adr;}*v[50005],*p;
int dist[50001],nrq[50001],n,m,i,x,y,c;
queue<int>Q;
bool ok;
int bellman_ford()
{int nd,c,j,d;
    Q.push(1);
    for(i=2;i<=n;i++) dist[i]=inf;
    while(!Q.empty())
    {
        nd=Q.front();
        d=dist[nd];
        p=v[nd];
        while(p)
        {
            j=p->info;
            c=p->c;
            if(d+c < dist[j])
            {
              dist[j] = d+c;
              nrq[j]++;
              if(nrq[j] == n) return 0;//daca un nod a fost bagat in coada de >n ori
              Q.push(j);
            }
            p=p->adr;
        }
        Q.pop();
    }
    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<<dist[i]<<" ";
    f.close();g.close();
  return 0;
}