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

using namespace std;

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

const int INF = 1e9;

int n,m,x,y,c;
vector<vector<pair<int,int>>> adj;
vector<int> dist;
vector<int> tata;

void bellmanford(int nod,int& flag){
    queue<int> q;
    vector<int> inQueue(n+1, 0);
    vector<int> cntPush(n+1, 0);

    q.push(nod);
    inQueue[nod] = 1;
    dist[nod] = 0;
    cntPush[nod] = 1;


    while(!q.empty() && flag == 0){
        int nod = q.front();
        q.pop();

        inQueue[nod] = 0;

        for(auto& [neigh, wt]: adj[nod]){
            if(dist[neigh] > wt + dist[nod]){
                dist[neigh] = wt + dist[nod];
                tata[neigh] = nod;

                if(inQueue[neigh] == 0){
                    inQueue[neigh] = 1;
                    q.push(neigh);

                    if(++cntPush[neigh] >= n){
                        flag = 1;
                        break;
                    }
                }
            }
        }
    }
}

int main(){
    f >> n >> m;
    dist.resize(n+1, INF);
    tata.resize(n+1, 0);
    adj.resize(n+1, vector<pair<int,int>>());
    for(int i=1; i<=m; i++){
        f >> x >> y >> c;
        adj[x].push_back(make_pair(y,c));
    }
    int flag = 0,endNode = 0;
    bellmanford(1, flag);
    if(flag == 1)
        g << "Ciclu negativ!";
    else{
        for(int i=2; i<=n; i++){
            g << dist[i] << " ";
        }
    }
    return 0;
}