#include <fstream>
#include <climits>
#include <queue>
#define w 5001
using namespace std;
int a[w][w];
queue <unsigned int> q;
bool viz[w];
int l[w],cnt[w];
int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int c,x,y,i,n,m,s;
    bool negc=0;
    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        l[i]=INT_MAX;
    }
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
    s=1;
    l[s]=0;viz[s]=1;q.push(s);
    while ((!q.empty())&&(!negc))
    {
        x=q.front();q.pop();
        viz[x]=0;
        for (i=1;i<=n;i++)
        {
            if (a[x][i] && l[i]>a[x][i]+l[x])
            {
                l[i]=a[x][i]+l[x];
                if (!viz[i])
                {
                    if (cnt[i]>n) negc=1;
                    else
                    {
                        q.push(i);
                        viz[i]=1;
                        cnt[i]++;
                    }
                }
            }
        }
    }
    if (negc)
    {
        g<<"Ciclu negativ\n";
    }
    else
    {
        for (i=1;i<=n;i++)
            g<<l[i]<<' ';
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}