#include <bits/stdc++.h>

using namespace std;
vector <pair <int,int>> v[50005];
int n,m,i,x,y,cost,dist[50005],viz[50005],lung[50005];
queue <int> q;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int main()
{

    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        v[x].push_back({y,cost});
    }
    for (i=1;i<=n;i++)
    {
        dist[i] = 1e9;
    }
    dist[1]=0;
    q.push(1);
    while (!q.empty())
    {
        int acum = q.front();
        q.pop();
        viz[acum]=0;
        for (int i=0;i<v[acum].size();i++)
        {
            int nod = v[acum][i].first;
            if (dist[nod] > dist[acum]+v[acum][i].second)
            {
                dist[nod] = dist[acum]+v[acum][i].second;
                if (viz[nod]==0)
                {
                    viz[nod]=1;
                    q.push(nod);
                }
                lung[nod]++;
                if (lung[nod]==n)
                {
                    g<<"Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for (i=2;i<=n;i++)
    {
        g<<dist[i]<<" ";
    }
    return 0;
}