#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=50005;
vector< pair<int, int> > adj[MAXN];
int main()
{
    ifstream in ("bellmanford.in");
    int n,m,i,x,y,c;
    in>>n>>m;
    for(i=0;i<m;++i)
    {
        in>>x>>y>>c;
        adj[x].push_back(make_pair(y,c));
    }
    in.close();
    queue <int> q;
    bitset <MAXN> inq(false);
    vector <int> dist(MAXN,INF),counter(MAXN,0);
    int negative=0;
    dist[1]=0;q.push(1);inq[1].flip();
    while(!q.empty() && !negative)
    {
        x=q.front();q.pop();inq[x]=false;
        vector< pair<int, int> >::iterator it;
        for(it=adj[x].begin();it!=adj[x].end();++it)
            if(dist[x]<INF)
                if(dist[it->first]>dist[x]+it->second)
                {
                    dist[it->first]=dist[x]+it->second;
                    if(!inq[it->first])
                    {
                        if(counter[it->first]>n) negative=1;
                        else
                        {
                            q.push(it->first);
                            inq[it->first]=true;
                            counter[it->first]++;
                        }
                    }
                }
    }
    ofstream out("bellmanford.out");
    if(negative)
        cout<<"Ciclu negativ!\n";
    else
        for(i=2;i<=n;++i)
            out<<dist[i]<<" ";
    out.close();
    return 0;

}