#include<stdio.h>
#define INF 0x3f3f3f3f
#define DIM 50005

int n,m;

typedef struct q_node{
    int val;
    q_node* next;
} Q_node;

typedef struct g_node{
    int node;
    int cost;
    g_node* next;
} G_node;

G_node *graph[DIM];

bool exist[DIM];
int best[DIM];
int distance[DIM];

class Queue{
    Q_node *beg,*end;
    int nr;
public:
    Queue():nr(0){};

    void push(int val);
    void pop();


    int front(){
        return beg->val;
    }
    bool empty(){
        return nr==0 ? true : false;
    }
    int size(){
        return nr;
    }
};

void Queue::push(int val){
    Q_node *temp;

    temp=new Q_node;
    temp->val=val;
    temp->next=NULL;

    if(nr){
        end->next=temp;
        end=temp;
    }else{
        beg=end=temp;
    }
    nr++;
}

void Queue::pop(){
    Q_node *temp;

    if(nr!=0){
        temp=beg;
        beg=beg->next;
        delete temp;

        nr--;
    }
}

void read(){
    int i,a,b,c;
    G_node *temp;

    scanf("%d %d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d %d %d",&a,&b,&c);
        temp=new G_node;
        temp->node=b;
        temp->cost=c;
        temp->next=graph[a];
        graph[a]=temp;
    }
    for(i=1;i<=n;i++){
        best[i]=INF;
    }
}

bool bellmanford(){
    int x;
    G_node *it;
    Queue Q;

    Q.push(1);
    exist[1]=true;
    best[1]=0;

    while(!Q.empty()){
        x=Q.front();
        it=graph[x];
        exist[x]=false;
        Q.pop();

        if(distance[x]>=n){
            return false;
        }else{
            while(it!=NULL){
            if(best[it->node]>best[x]+it->cost){
                best[it->node]=best[x]+it->cost;
                distance[it->node]=distance[x]+1;
                if(!exist[it->node]){
                    Q.push(it->node);
                    exist[it->node]=true;
                }
            }
            it=it->next;
            }
        }
    }

    return true;
}

void write(bool ok){
    int i;
    if(!ok){
        printf("Ciclu negativ!");
    }else{
        for(i=2;i<=n;i++){
            printf("%d ",best[i]);
        }
    }
    printf("\n");
}

int main(){
    bool ok;

    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    read();
    ok=bellmanford();
    write(ok);

    return 0;
}