#include <fstream>
#include <utility>
#include <vector>
using namespace std;
int d[50003],n,m;
vector< pair<int,int> >G[50003];
void init()
{
    int i;
    for(i=1;i<=n;i++) d[i]=int(2e9);
    d[1]=0;
}
void bellman()
{
    int t,i,j,x;
    t=n-1;
    while(t--)
    {
        for(i=1;i<=n;i++)
        {
            x=G[i].size();
            for(j=0;j<x;j++)
            if(d[G[i][j].first]>d[i]+G[i][j].second)
                d[G[i][j].first]=d[i]+G[i][j].second;
        }
    }
}
bool check()
{
    int i,j,x;
    for(i=1;i<=n;i++)
    {
        x=G[i].size();
        for(j=0;j<x;j++)
        if(d[G[i][j].first]>d[i]+G[i][j].second)
            return 1;
    }
    return 0;

}
int main()
{
    int x,y,c,i;
    ifstream fi("bellmanford.in");
    ofstream fo("bellmanford.out");
    fi>>n>>m;
    for(i=1;i<=m;i++)
    {
        fi>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    init();
    bellman();
    if(check()) fo<<"Ciclu negativ!\n"; else for(i=2;i<=n;i++) fo<<d[i]<<" ";
    return 0;
}