#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
#define N 50005
#define INF 1e9
vector < pair < int, int> > vec[N];
queue <int> Q;
int n,m,d[N];
bool inQueue[N];
int cnt_inQueue[N];
void read()
{
    int i,j,x,y,c;
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        vec[x].push_back({y,c});
    }
}
void solve()
{
    int i,j,to,cost,from,nod;
    bool has_cycle=false;
    for(i=1; i<=n; i++)
        d[i]=INF;
    d[1]=0;
    inQueue[1]=true;
    cnt_inQueue[1]++;
    Q.push(1);
    while(Q.empty()==false && has_cycle==false)
    {
        from=Q.front();
        Q.pop();
        inQueue[from]=false;
        for(auto x:vec[from])
        {
            to=x.first;
            cost=x.second;
            if(d[to]>d[from]+cost)
            {
                d[to]=d[from]+cost;
                //if(inQueue[to]==false)
                {
                    if(cnt_inQueue[to]>n)
                        has_cycle=true;
                    else
                    {
                        Q.push(to);
                        inQueue[to]=true;
                        cnt_inQueue[to]++;
                    }
                }
            }

        }
    }
    if(has_cycle==false)
    {
        for(i=2; i<=n; i++)
            cout<<d[i]<<" ";
    }
    else
        cout<<"Ciclu negativ!";
}
int main()
{
    read();
    solve();
    return 0;
}