#include<vector>
#include<fstream>
//#include<iostream>
#define oo 1e9
using namespace std;
struct muchie
{
    int x,y,c;
}m[250001];
//vector<muchie> m;
int n,M;
void citire()
{
    ifstream f("bellmanford.in");
    f>>n>>M;

    for(int i=1;i<=M;i++)
    {
        f>>m[i].x>>m[i].y>>m[i].c;
    }
    f.close();
}
vector<int> d;
void Bellman_Ford(int p, bool &ngcl)
{

    d[p]=0;
    for(int i=1;i<=n-1;i++)
    { bool changed=false;
        for(int j=1;j<=M;j++)
        {
            int x,y,c;
            x=m[j].x;
            y=m[j].y;
            c=m[j].c;
            if(d[x]!=oo&&d[x]+c<d[y])
            {
                d[y]=d[x]+c;
                changed=true;
            }
        }
        if(changed==false) break;
    }
    for(int j=1;j<=M;j++)
    {
        int x,y,c;
            x=m[j].x;
            y=m[j].y;
            c=m[j].c;
            if(d[x]!=oo&&d[x]+c<d[y])
            {
                ngcl=true;
                break;
            }
    }
}
int main()
{
    citire();
    d.resize(n+1,oo);
    bool ngcl=false;
    Bellman_Ford(1,ngcl);
    ofstream g("bellmanford.out");
    if(ngcl==true)
    {
        g<<"Ciclu negativ";
    }
    else
    {
        for(int i=2;i<=n;i++)
            g<<d[i]<<" ";
    }
    g.close();
    return 0;
}