#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, flag = 0;
vector<vector<pair<int,int>>> adj;
vector<int> dist;
vector<int> tata;

void bellman_ford(){
    queue<int> q;
    vector<int> inQueue(n+1, 0);
    vector<int> cntQueue(n+1, 0);

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

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

        inQueue[nod] = 0;

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

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

                    q.push(neigh);

                    if(++cntQueue[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({y,c});
    }

    bellman_ford();
    if(flag == -1){
        g << "Ciclu negativ!";
    }
    else{
        for(int i=2; i<=n; i++){
            g << dist[i] << " ";
        }
    }


    return 0;
}