#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

#define INF 1e9

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");


const int NMAX=50005;

vector<pair<int,int>> v[NMAX];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int> > > h;
int nod,d[NMAX], g[NMAX];

int main()
{
    int i,j,n, m,a, b, c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[a].push_back({c,b});
    }
    for(i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    h.push({0,1});
    while(!h.empty())
    {
        nod=h.top().second;
        h.pop();
        for(i=0;i<v[nod].size();i++)
        {
            if(d[nod]+v[nod][i].first<d[v[nod][i].second])
            {
                g[v[nod][i].second]++;
                d[v[nod][i].second]=d[nod]+v[nod][i].first;
                h.push({d[v[nod][i].second],v[nod][i].second});
                if(g[v[nod][i].second] == n)
                {
                   fout<<"Ciclu negativ!\n";
                   return 0;
                }
            }
        }
    }
    for(i=2;i<=n;i++)
        fout<<d[i] << ' ';
    return 0;
}