#include <fstream>
#include<queue>
#include<vector>
using namespace std;
ifstream f("bellmanford.in"); ofstream g("bellmanford.out");
const int NMAX = 50005;
const int INF = 1e9;
vector < pair <int,int> >gr[NMAX];
int n,m,start,dist[NMAX],nr[NMAX];
queue <int> q;
bool viz[NMAX];
bool Bellman_Ford()
{   bool cicle=false;
    while(!q.empty() && !cicle)
    {   int nod=q.front();
        q.pop();
        for(int i=0;i<gr[nod].size();i++) ///parcurg lista de vecini
        {   if(nr[gr[nod][i].second]>n) cicle=true; ///fac cum a zis profesoara doar ca folosec un vector in plus
            if(dist[nod]+gr[nod][i].first<dist[gr[nod][i].second])
            {   dist[gr[nod][i].second]=dist[nod]+gr[nod][i].first; ///principiul drumului minim
                if(!viz[gr[nod][i].second])
                {   q.push(gr[nod][i].second); ///folosirea cozii de la BFS pt bellman-ford
                    viz[gr[nod][i].second]=true;
                }
                nr[gr[nod][i].second]=nr[nod]+1;
                if(nr[gr[nod][i].second]>n) cicle=true; ///aceeasi chestie ca mai sus
            }
        }
    }
    return cicle;
}
int main()
{   f>>n>>m;
    for(int x,y,cost,i=1;i<=m;i++)
    {   f>>x>>y>>cost; ///de la x la y am costul dat
        gr[x].push_back(make_pair(cost,y)); ///in vectorul gr pun costul si y => legatura dintre x si y cu un costr dat
    }
    for(int i=1;i<=n;i++) dist[i]=INF;
    viz[1]=true; nr[1]=1;
    q.push(1); dist[1]=0;
    if(Bellman_Ford())
    {   g<<"Ciclu negativ"; return 0; }
    else for(int i=2;i<=n;i++) g<<dist[i]<<" ";
    return 0;
}