#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
int n,m,a,b,c,dp[50005],ap[50005];
vector<pair<int,int> > v[50005];
priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; 
void bell()
{
    q.push({dp[1],1});
    while (!q.empty())
    {
        pair<int,int> t1=q.top();
        int t=t1.second;
        q.pop();
        ap[t]++;
        if (ap[t]>n+3) {cout<<"Ciclu negativ!"; return ;}
        for (int j=0;j<v[t].size();++j)
        {
            if (dp[t]+v[t][j].second<dp[v[t][j].first]) {dp[v[t][j].first]=dp[t]+v[t][j].second; q.push({dp[v[t][j].first],v[t][j].first});}
        }
    }
    for (int i=2;i<=n;++i)
    cout<<dp[i]<<" ";
}
int main() {
    cin>>n>>m;
    for (int i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        v[a].push_back({b,c});
    }
    for (int i=2;i<=n;++i)
    dp[i]=1000000000;
    bell();
    return 0;
}