#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,i,j,d[50001],x,y,c;
const int INF=2e9;
vector<pair<int,int>>v[50001];
queue<int>q;
bool inqueue[50001];
int nrap[50001];
int main()
{
    fin>>n>>m;
    fill(d+2,d+n+1,INF);
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({c,y});
    }
    q.push(1);
    while(!q.empty())
    {
        int nod=q.front();
        for(i=0;i<v[nod].size();i++)
        {
            pair<int,int>vecin=v[nod][i];
            if(d[vecin.second]>d[nod]+vecin.first)
                {
                    d[vecin.second]=d[nod]+vecin.first;
                    if(!inqueue[vecin.second])
                    {
                        q.push(vecin.second);
                        inqueue[vecin.second]=true;
                        nrap[vecin.second]++;
                        if(nrap[vecin.second]==n)
                        {
                            fout<<"Ciclu negativ!";
                            return 0;
                        }
                    }
                }
        }
        inqueue[q.front()]=false;
        q.pop();
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";

}