#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define LMAX 100005
vector<PII> E[LMAX];
int n,D[LMAX],viz[LMAX];
void Djikstra(int k){
    priority_queue<PII,vector<PII>,greater<PII>> Q;
    Q.push({0,k});
    D[k]=0;
    while(!Q.empty()){
        int len=Q.top().first,nod=Q.top().second;
        Q.pop();
        if(len!=D[nod])
            continue;
        ++viz[nod];
        if(viz[nod]==n){
            printf("Ciclu negativ!");
            exit(0);
        }
        for(auto it : E[nod])
            if(len+it.second<D[it.first]){
                D[it.first]=len+it.second;
                Q.push({D[it.first],it.first});
            }
    }
}
int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        int st,dr,len;
        scanf("%d %d %d",&st,&dr,&len);
        E[st].push_back({dr,len});
    }
    for(int i=2;i<=n;++i)
        D[i]=INT_MAX;
    Djikstra(1);
    for(int i=2;i<=n;++i)
        if(D[i]==INT_MAX)
            printf("0 ");
        else printf("%d ",D[i]);
    return 0;
}