#include <bits/stdc++.h>

using namespace std;

deque <int> q;

int l[50005];

vector <int> s[50005];
vector <int> p[50005];

int r[50005],iq[50005];

int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int n,m,x,y,c;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y>>c;
        s[x].push_back(y);
        //s[y].push_back(x);
        p[x].push_back(c);
        //p[y].push_back(c);
    }
    q.push_back(1);
    for(int i=1;i<=n;++i)
    {
        l[i]=INT_MAX;
    }
    l[1]=0;
    iq[1]=1;
    while(q.size())
    {
        for(int i=0;i<s[q.front()].size();++i)
        {
            int pct=s[q.front()][i],prc=p[q.front()][i]+l[q.front()];
            if(prc<l[pct])
            {
                r[pct]++;
                if(r[pct]>n)
                {
                    cout<<"Ciclu negativ!";
                    return 0;
                }

                l[pct]=prc;
                if(iq[pct]==0)
                {
                q.push_back(pct);
                iq[pct]=1;
                }
            }
        }
        iq[q.front()]=0;
        q.pop_front();
    }
    for(int i=2;i<=n;++i)
    {
        cout<<l[i]<<" ";
    }
    return 0;
}