#include <bits/stdc++.h>

#define NMAX 50005

using namespace std;

int n,m;
int viz[NMAX],cost[NMAX];
vector<pair<int,int> > g[NMAX];


void read()
{
    int a,b,c;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        g[a].push_back(make_pair(c,b));
    }
}

void bellmanford()
{
    queue<int> q;
    for(int i=2;i<=n;++i)
        cost[i]=0x3f3f3f3f;
    q.push(1);
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        vector<pair<int,int> >::iterator it;
        for(it=g[k].begin();it!=g[k].end();++it)
        {
            if(cost[it->second]>cost[k]+it->first)
            {
                ++viz[it->second];
                if(viz[it->second]>=n)
                {
                    cout<<"Ciclu negativ!\n";
                    return;
                }
                cost[it->second]=cost[k]+it->first;
                q.push(it->second);
            }
        }
    }
    for(int i=2;i<=n;++i)
        cout<<cost[i]<<" ";
    cout<<"\n";
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    read();
    bellmanford();
    return 0;
}