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

using namespace std;

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

vector < vector < pair<int , int> > > gr(50100);
vector < int > dist(50100);
vector < int > viz(50100);
vector < int > used(50100);

queue <int> Q;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n , m;
    cin>>n>>m;

    for (int i=1; i<=m; i++){
        int a , b , val;
        cin>>a>>b>>val;

        gr[a].push_back({b , val});

    }

    for (int i=2; i<=n; i++){
        dist[i] = 2e9;
    }

    Q.push(1);

    while (!Q.empty()){

        int now = Q.front();
        Q.pop();
        viz[now]++;
        used[now] = false;

        if (viz[now] > n){
            cout<<"Ciclu negativ!";
            return 0;
        }

        for (auto &x : gr[now]){
            if (dist[x.first] > dist[now] + x.second){
                dist[x.first] = dist[now] + x.second;
                if (!used[x.first]){
                    Q.push(x.first);
                    used[x.first] = true;
                }
                else{
                    viz[x.first]++;
                }
            }
        }

    }

    for (int i=2; i<=n; i++){
        cout<<dist[i]<<" ";
    }

    return 0;
}