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

using namespace std;

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

const int size = 5e4+5;

const int inf = 1e9;

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

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

int n, m, d[size], viz[size], cnt[size];

void BF(int sursa){
    for(int i=1;i<=n;i++)
        d[i] = inf;
    d[sursa] = 0;
    viz[sursa] = 1;
    cnt[sursa]++;
    pair<int, int> k;
    pq.push({0, 1});
    while(!pq.empty()){
        k = pq.top();
        pq.pop();
        viz[k.second] = 0;
        for(auto it:v[k.second])
            if(d[it.second] > d[k.second] + it.first){
                d[it.second] = d[k.second] + it.first;
                if(viz[it.second] == 0){
                    viz[it.second] = 1;
                    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;
}