#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct str{
    int nod,cost;
    bool operator<(const str &other) const{
        return cost>other.cost;
    }
};
priority_queue <str> co;
vector <str> v[50003];
int n,m,cst[50003];
int fr[50002];
int main()
{
    bool ex=false;
    int x,y,c;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(int i=0;i<=n;i++)
    {
        cst[i]=50000*20001;
    }
    co.push({1,0});
    cst[1]=0;
    fr[1]=1;
    while(!co.empty())
    {
        int z=co.top().nod;
        int cc=co.top().cost;
        co.pop();
        for(int i=0;i<v[z].size();i++)
        {
            if(cst[v[z][i].nod]>cst[z]+v[z][i].cost)
            {
                if(cst[v[z][i].nod]!=50000*20001&&cst[z]+v[z][i].cost<=0)
                {
                    ex=true;
                }
                cst[v[z][i].nod]=cst[z]+v[z][i].cost;
                if(fr[v[z][i].nod]<n-1)
                {
                co.push({v[z][i].nod,cst[v[z][i].nod]});
                fr[v[z][i].nod]++;
                }

            }
            if(ex==true)
                break;
        }
        if(ex==true)
            break;
    }
    if(ex==true)
    {
        g<<"Ciclu negativ!";
    }
    else
    for(int i=2;i<=n;i++)
    {
        if(cst[i]==50000*20001)
            cst[i]=0;
        g<<cst[i]<<" ";
    }

    return 0;
}