#include <fstream>
#define INFINIT 2000000000
using namespace std;

int incoada[50009], verf[50009],coada[500000], d[50009], n, m;

struct nod{int vc, cost; nod * urm;};
typedef struct nod * lista;
lista vf[500009], ultim[50009], t;
void adauga(lista &prim, lista &u, int k, int c){
    lista q= new nod;
    q->cost=c;
    q->vc=k;
    if(!u){
        q->urm=NULL;
        prim=q;
        u=prim;
    }else{
        q->urm=u->urm;
        u->urm=q;
        u=u->urm;
    }
}
int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    int i, ok=1, x, y, c, p, u;

    fin>>n>>m;
    for(i=0;i<m; i++){
        fin>>x>>y>>c;
        adauga(vf[x], ultim[x], y, c);
        adauga(vf[y], ultim[y], x, c);
    }
    //for(t=vf[1]; t; t=t->urm)  fout<<"Vecin:"<<t->vc<<"  Cost:"<<t->cost<<endl;

    for(i=1; i<=n; i++) d[i]=INFINIT;
    d[1]=0; incoada[1]=1; verf[1]=1;
    p=u=0;
    coada[p]=1;

    while(p<=u and ok){
        x=coada[p];
        p++;
        incoada[x]=0;
        for(t=vf[x]; t; t=t->urm){
            y=t->vc;
            if(d[y]>d[x]+t->cost){
                d[y]=d[x]+t->cost;
                //t[t->vc]=x;
                if(!incoada[y]){
                    u++;
                    coada[u]=y;
                    incoada[y]=1;
                    verf[y]++;
                    if(verf[y]>n)ok=0;
                }
            }
        }
    }
    if(ok==0)
        fout<<"Ciclu negativ!";
    else
        for(i=2; i<=n; i++) fout<<d[i]<<" ";


    return 0;
}