#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;
#define INFI 0x3f3f3f3f
#define DM 250001
#define DN 50001

struct nod {
    int x,cost;
    nod *urm;
}*v[DN];

deque <int> coada;
int m,n,dist[DN],viz[DN],aparitii[DN];

void adaugare(int x,int y,int cost) {
    nod *p;
    p=new nod;
    p->cost=cost;
    p->x=y;
    p->urm=v[x];
    v[x]=p;
}

bool bellman_ford() {
    nod *p;
    coada.push_back(1);
    for( ;coada.size();coada.pop_front() ) {
        viz[coada.front()]=0;
        for(p=v[coada.front()]; p!=NULL; p=p->urm)
            if(dist[p->x]>dist[coada.front()]+p->cost) {
                dist[p->x]=dist[coada.front()]+p->cost;
                if(!viz[p->x]) {
                    viz[p->x]=1;
                    if(aparitii[p->x]>n) return false;
                    ++aparitii[p->x];
                    coada.push_back(p->x);
                }
            }
    }
    return true;
}

void initializareSU() {
    for(int i=1; i<=n; i++)
        dist[i]=INFI,viz[i]=0,aparitii[i]=0;
    dist[1]=0;
    viz[1]=1;
    ++aparitii[1];
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int i,x,y,c;
    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++)
        scanf("%d %d %d",&x,&y,&c), adaugare(x,y,c);
    initializareSU();
    if(!bellman_ford()) printf("Ciclu negativ!\n");
    else for(i=2; i<=n; i++) printf("%d ",dist[i]);
    return 0;
}