#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
struct bine { int nod ; int edge ;};
vector<bine>lista[50001];
queue<int>q;
int nr[50001];
int dist[50001];
bool viz[50001];
int n,m;
void citire(){
    int i,a,b,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        lista[a].push_back ({b,c});
    }
}
int pp=1;
void bellmanford(int nod){
    int p,i;
    for(i=1;i<=n;i++)
        dist[i]=999999999;
    dist[nod]=0;
    viz[nod]=1;
    q.push(nod);
    while(!q.empty()&&pp==1){
        p=q.front();
        q.pop();
        viz[p]=0;
        for(i=0;i<lista[p].size()&&pp==1;i++){
            if(dist[p]+lista[p][i].edge<dist[lista[p][i].nod]){
                dist[lista[p][i].nod]=dist[p]+lista[p][i].edge;
                if(viz[lista[p][i].nod]==0){
                    q.push(lista[p][i].nod);
                    nr[lista[p][i].nod]++;
                    viz[lista[p][i].nod]=1;
                }
            }
            if(nr[lista[p][i].nod]>n){
                printf("Ciclu negativ!");
                pp=0;
            }
        }
    }
}
int main(){
    int i;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    citire();
    bellmanford(1);
    for(i=2;i<=n&&pp==1;i++)
        printf("%d ",dist[i]);
    return 0;
}