#include<fstream>
#include<cstring>
#include<queue>
#define In "bellmanford.in"
#define Out "bellmanford.out"
#define nod first
#define cost second
#define Nmax 50004
#define INF 0x3f3f3f3f
using namespace std;
int n;
vector< pair<int ,int > >graf[Nmax];
queue< int >Q;
int uz[Nmax],Dist[Nmax];
bool ciclu_negativ,in_queue[Nmax];
ofstream g(Out);
inline void Citire()
{
    int m,x,y,c;
    ifstream f(In);
    f>>n>>m;
    while(m--)
    {
        f>>x>>y>>c;
        graf[x].push_back(make_pair(y,c));
    }
    f.close();
}

inline void Algoritm_Bellman_Ford()
{
    memset( Dist, INF, sizeof(Dist) );
    Dist[1] = 0;
    Q.push(1);
    in_queue[1] = true;
    int act;
    vector< pair< int ,int > >::iterator it;
    pair< int, int > vecin;
    while(!Q.empty())
    {
        act = Q.front();
        Q.pop();
        in_queue[act] = false;
        for(it = graf[act].begin();it!=graf[act].end();it++)
        {
            vecin = *it;
            if(Dist[vecin.nod]>Dist[act]+vecin.cost)
            {
                Dist[vecin.nod] = Dist[act]+vecin.cost;
                if(in_queue[vecin.nod]==false)
                    Q.push(vecin.nod);
                if(++uz[vecin.nod]==n)
                {
                    ciclu_negativ = true;
                    return ;
                }
            }
        }
    }
}

int main()
{
    Citire();
    Algoritm_Bellman_Ford();
    if(ciclu_negativ)
        g<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            g<<Dist[i]<<" ";
    g<<"\n";
    g.close();
    return 0;
}