#include <iostream>
#include <fstream>
using namespace std;
#define INF 50000000
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
struct nod{
int inf;
int c;
nod * next;};
nod * graf[50005];
void add(int x,int y,int c)
{
    nod * p;
    p=new nod;
    p->inf=y;
    p->c=c;
    p->next=graf[x];
    graf[x]=p;
}
void citire(int &n,int &m)
{
    in>>n>>m;
    int i,x,y,c;
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        add(x,y,c);
    }
}
void afisare(int n)
{
    nod * p;
    int i;
    for(i=1;i<=n;i++)
    {
        p=graf[i];
        out<<i<<' ';
        while(p)
        {
            out<<p->inf<<' '<<p->c<<"   ";
            p=p->next;
        }
        out<<'\n';
    }
}
int distanta[50002];
void afisare2(int n)
{
    int i;
    for(i=2;i<=n;i++)
        out<<distanta[i]<<' ';
    out<<'\n';
}
int vizitat[50002];
int coada[50002];
void bellman_ford(int n)
{
    int ok=1;
    int i;
    for(i=1;i<=n;i++)
        distanta[i]=INF;
    distanta[1]=0;
    int inc,sf;
    inc=sf=1;
    coada[inc]=1;
    while(ok and inc<=sf)
    {
        nod * p;
        p=graf[coada[inc]];
        while(p)
        {
            if(vizitat[p->inf]>n)
                ok=0;
            else
                if(distanta[p->inf]>distanta[coada[inc]]+p->c)
              {

                distanta[p->inf]=distanta[coada[inc]]+p->c;
            sf++;
            coada[sf]=p->inf;
            vizitat[p->inf]++;
            }
            p=p->next;
        }
        inc++;
    }
    if(!ok)
        out<<"Ciclu negativ!";
    else
        afisare2(n);


}
int main()
{
    int n,m;
    citire(n,m);
    bellman_ford(n);
    return 0;
}