#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define pb push_back
#define inf 2e9

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector <pair<int,int> > v[50001];
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > h; // min-heap
int n,m,d[50001],a,b,c,viz[50001];

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[a].pb({c,b});
    }
    // d[1]=0
    for(int i=2;i<=n;i++)
    {
        d[i]=inf;
    }
    h.push({0,1});
    while(!h.empty())
    {
        int nod=h.top().second;
        h.pop();
        // dispare if(viz..)
        for(int i=0;i<v[nod].size();i++)
        {
            int next = v[nod][i].second;
            int cost = v[nod][i].first;
            if(d[nod]+cost<d[next])
            {
                viz[next]++;
                d[next]=d[nod]+cost;
                h.push({d[next],next});
                if(viz[next]==n)
                {
                    fout<<"Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";
}