#include <fstream>
#include <deque>
#include <vector>
#define f first
#define s second

using namespace std;

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

int n,m,i,x,vec,y,c,nr[50005],d[50005];
bool v[50005];
deque <int>dq;
vector <pair <int,int> >a[50005];

int main()
{
    fin >> n >> m;
    for (i=1;i<=n;i++)
    {
        fin >> x >> y >> c;
        a[x].push_back({y,c});
    }
    for (i=1;i<=n;i++) d[i]=2000000005;
    d[1]=0;
    v[1]=1;
    dq.push_back(1);
    while (dq.empty()!=1)
    {
        x=dq.front();
        for (i=0;i<a[x].size();i++)
        {
            vec=a[x][i].f;
            c=a[x][i].s;
            if (d[x]+c<d[vec])
            {
                d[vec]=d[x]+c;
                if (v[vec]==0)
                {
                    v[vec]=1;
                    dq.push_back(vec);
                    nr[vec]++;
                    if (nr[vec]>=n)
                    {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
        v[x]=0;
        dq.pop_front();
    }
    for (i=2;i<=n;i++) fout << d[i] << " ";

    return 0;
}