#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int N=50001;
const int INF=200000000;
vector<int>a[N];
vector<int>c[N];
int n,m,d[N],nrapar[N];
bool apar[N];
queue<int>coada;
int main()
{
    int x,y,cost;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>cost;
        a[x].push_back(y);
        c[x].push_back(cost);
    }
    for(int i=2;i<=n;i++)
        d[i]=INF;
    coada.push(1);
    apar[1]=true;
    nrapar[1]++;
    while(!coada.empty())
    {
        x=coada.front();
        coada.pop();
        apar[x]=false;
        for(unsigned i=0;i<a[x].size();i++)
        {
            y=a[x][i];
            cost=c[x][i];
            if(d[x]+cost<d[y])
            {
                d[y]=d[x]+cost;
                if(!apar[y])
                {
                    coada.push(y);
                    apar[y]=true;
                    nrapar[y]++;
                    if(nrapar[y]==n)
                    {
                        out<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for(int i=2;i<=n;i++)
        out<<d[i]<<' ';
    return 0;
}