#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int x, y, w;
};
vector<edge> edges;
int n, m;
void read()
{
    ifstream f("bellmanford.in");
    f>>n>>m;
    edge e;
    while(f>>e.x>>e.y>>e.w)
        edges.push_back(e);
    f.close();
}
pair<bool, vector<int>> Bellman_Ford(int x=1)
{
    vector<int> distance(n+1);
    bool negative_cycle=0;
    for(int i=1;i<=n;i++)
        distance[i]=10001;
    distance[x]=0;

    for(int i=1;i<n;i++)
        for(auto a:edges)
            distance[a.y]=min(distance[a.y], distance[a.x]+a.w);
    for(auto a:edges)
        if(distance[a.x]+a.w<distance[a.y])
            negative_cycle=1;
    return make_pair(negative_cycle, distance);
}
int main()
{
    read();
    pair<bool, vector<int>> res=Bellman_Ford();
    ofstream g("bellmanford.out");
    if(res.first)
        g<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            g<<res.second[i]<<' ';
    g.close();
    return 0;
}