#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
const int N = 50009,Inf = 0x3f3f3f3f;
int n,m,a,b,c;
int dist[N];
struct muchie
{
    int x,y,c;
};
vector<muchie> muchii;
int main()
{
    cin>>n>>m;
    while(m--)
    {
        cin>>a>>b>>c;
        muchii.push_back({a,b,c});
    }

    memset(dist,Inf,sizeof(dist));
    dist[1] = 0;
    for(int i = 1; i < n; ++i)
        for(auto mc : muchii)
            if(dist[mc.y] > dist[mc.x] + mc.c)
                dist[mc.y] = dist[mc.x] + mc.c;

    for(auto mc : muchii)
        if(dist[mc.y] > dist[mc.x] + mc.c)
        {
            cout<<"Ciclu negativ!";
            return 0;
        }

    for(int i = 2; i <= n; ++i)
        cout<<dist[i]<<' ';
    return 0;
}