#include <bits/stdc++.h>
#define LMAX 100005
using namespace std;
bool in_queue[LMAX];
int n,dist[LMAX],viz[LMAX];
void Init(){
    for(int i=1;i<=n;++i)
        dist[i]=INT_MAX;
}
vector<pair<int,int> > G[LMAX];
void BFord(int nod){
    queue<int> Q;
    dist[nod]=0;
    Q.push(nod);
    while(!Q.empty()){
        int nod=Q.front();
        Q.pop();
        in_queue[nod]=0;
        ++viz[nod];
        if(viz[nod]==n){
            printf("Ciclu negativ!\n");
            exit(0);
        }
        for(auto it : G[nod])
            if(dist[nod]+it.second<dist[it.first]){
                dist[it.first]=dist[nod]+it.second;
                if(!in_queue[it.first]){
                    Q.push(it.first);
                    in_queue[it.first]=1;
                }
            }
    }
}
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 u,v,cost;
        scanf("%d %d %d",&u,&v,&cost);
        G[u].push_back({v,cost});
    }
    Init();
    BFord(1);
    for(int i=2;i<=n;++i)
        printf("%d ",dist[i]);
    return 0;
}