#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int inf = 1e9;

vector <pair<int, int>> v[50005];

priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int n, m, d[50005], cnt[50005];

void BF(int sursa){
    for(int i=1;i<=n;i++)
        d[i] = inf;
    d[sursa] = 0;
    cnt[sursa]++;
    pair<int, int> k;
    pq.push({0, 1});
    while(!pq.empty()){
        k = pq.top();
        pq.pop();
        if(d[k.second] < k.first) continue;
        for(auto it:v[k.second])
            if(d[it.second] > d[k.second] + it.first){
                d[it.second] = d[k.second] + it.first;
                pq.push({d[it.second], it.second});
                cnt[it.second]++;
                if(cnt[it.second] == n){
                    out<<"Ciclu negativ!";
                    exit(0);
                }
            }
    }
}

int main(){
    int x, y, c;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>c;
        v[x].push_back({c, y});
    }
    BF(1);
    for(int i=2;i<=n;i++)
        out<<d[i]<<" ";
    return 0;
}