#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

int n, m;
const int INF = 1e9;
vi d(50005, INF), cnt(50005);
vector<bool> in_queue(50005);
vector<vector<pi>> adj(50005);
queue<int> q;

void solve(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].pb({b, c});
    }
    d[1] = 0; q.push(1); in_queue[1] = 1;
    bool negative_cycle = false;
    while(!q.empty() && !negative_cycle){
        int x = q.front();
        q.pop();
        in_queue[x] = 0;
        for(int i = 0; i < adj[x].size(); i++){
            if(d[adj[x][i].f] > d[x] + adj[x][i].s){
                d[adj[x][i].f] = d[x] + adj[x][i].s;
                if(!in_queue[adj[x][i].f]){
                    if(cnt[adj[x][i].f] > n)
                        negative_cycle = true;
                    else {
                        q.push(adj[x][i].f);
                        cnt[adj[x][i].f]++;
                        in_queue[adj[x][i].f] = 1;
                    }
                }
            }
        }
    }
    if(negative_cycle){
        cout << "Ciclu negativ!\n";
        return;
    }
    for(int i = 2; i <= n; i++)
        cout << d[i] << ' ';
    cout << '\n';
}  
 
int main(){
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}