#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll NMAX=5e4+5;
set<pll> s;
ll dist[NMAX],times_added[NMAX];
bool in_queue[NMAX];
vector<pll> edg[NMAX];
int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    ll n,m;
    fin>>n>>m;
    for(ll i=0;i<m;i++){
        ll u,v,c;
        fin>>u>>v>>c;
        u--,v--;
        edg[u].push_back({v,c});
    }
    queue<ll> q;
    for(ll i=1;i<n;i++) dist[i]=1e12;
    bool negative_cycle=0;
    q.push(0); in_queue[0]=1,++times_added[0];
    while(!q.empty() && !negative_cycle){
        ll u=q.front();
        q.pop();
        in_queue[u]=0;
        for(auto it : edg[u]){
            if(dist[u]+it.second<dist[it.first]){
                dist[it.first]=dist[u]+it.second;
                if(in_queue[it.first]) continue;
                if(times_added[it.first]>n){
                    negative_cycle=1;
                    break;
                }
                else{
                    ++times_added[it.first];
                    in_queue[it.first]=1;
                    q.push(it.first);
                }
            }
        }
    }
    if(negative_cycle){
        fout<<"Ciclu negativ!";
        return 0;
    }
    for(ll i=1;i<n;i++)
        fout<<dist[i]<<' ';
    return 0;
}