#include <iostream>
#include<bits/stdc++.h>

using namespace std;


ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int nmax=50001;
int n,m,x,y,c;

vector<vector<pair<int,int> > > graf;
priority_queue<pair<int,int>> q;


int main()
{
    fin>>n>>m;
    graf.assign(n+1,vector<pair<int,int>>());
    for(int i=0;i<m;i++){
        fin>>x>>y>>c;
       graf[x].push_back({c,y});
    }
    bitset<nmax> vas;
    vector<int> cou(n+1,0),dist(n+1,(int)1e9+1);
    dist[1]=0;
    q.push({0,1});
    while(!q.empty()){
        x=q.top().second;
        c=-q.top().first;
        q.pop();
        vas[x]=0;
        for(auto i:graf[x]){
            if(dist[i.second]>dist[x]+i.first){
                dist[i.second]=i.first+dist[x];
                if(!vas[i.second]){
                    vas[i.second]=1;
                    cou[i.second]++;
                    q.push({-dist[i.second],i.second});
                    if(cou[i.second]>n){fout<<"Ciclu negativ!"; return 0;}
                }
            }
        }
    }
    for(int i=2;i<=n;i++)fout<<dist[i]<<" ";
}