#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int N=25e4+1,inf=2e9;
struct elem
{
    int x,y,cost;
    bool operator<(const elem &e) const
    {
        return cost<e.cost;
    }
};
int n,m,x,y,c,i,j,d[N];
vector<elem> edge;
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;++i)
        d[i]=inf;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        edge.push_back({x,y,c});
        //edge.push_back({y,x,c});
    }
    int cycle=1;
    d[1]=0;
    while(cycle<=n)
    {
        int ok=0;
        for(auto e:edge)
        {
            x=e.x;
            y=e.y;
            c=e.cost;
            if(d[x]!=inf)
            {
                if(d[y]>d[x]+c)
                {
                    d[y]=d[x]+c;
                    ok=1;
                }
            }
        }
        if(!ok) break;
        cycle++;
    }
    if(cycle>n)
    {
        fout<<"Ciclu negativ!";
        return 0;
    }
    for(int i=2;i<=n;++i)
        fout<<d[i]<<' ';
    return 0;
}