#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m,x,y,u[50010],d[50010],cost;
vector<vector<pair<int,int>>>a;
queue<int>c;
bool v[50010];
int main()
{
    in>>n>>m;
    a.resize(n+5);
    for(int i=1;i<=n;++i)
        d[i]=1000000000;
    d[1]=0;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y>>cost;
        if(y!=1)
            a[x].push_back(make_pair(y,cost));
    }
    c.push(1);
    while(!c.empty())
    {
        int x=c.front();
        c.pop();
        v[x]=false;
        for(auto y:a[x])
        {
            if(d[y.first]>d[x]+y.second)
            {
                ++u[y.first];
                if(u[y.first]==n)
                {
                    out<<"Ciclu negativ!";
                    return 0;
                }
                d[y.first]=d[x]+y.second;
                if(v[y.first]==false)
                {
                    c.push(y.first);
                    v[y.first]=true;
                }
            }
        }
    }
    for(int i=2;i<=n;++i)
        out<<d[i]<<' ';
    return 0;
}