#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int NMAX=50001;
queue <pair<int,int>> q;
int visited[NMAX];
int d[NMAX];
bool inq[NMAX];
vector <pair<int,int>> graph[NMAX];
int main()
{
    int n,m,x,y,cost;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y>>cost;
        graph[x].push_back(make_pair(y,cost));
    }
    for(int i=1; i<=n; i++)
    {
        d[i]=-1;
    }

    q.push(make_pair(1,0));
    visited[1]=1;
    d[1]=0;
    inq[1]=1;
    while(!q.empty())
    {
        x=q.front().first;
        q.pop();
        inq[x]=0;
        for(unsigned int i=0; i<graph[x].size(); i++)
        {
            y=graph[x][i].first;
            cost=graph[x][i].second;
            if(d[y]>d[x]+cost || d[y]==-1)
            {
                d[y]=d[x]+cost;
                q.push(make_pair(y,d[y]));
                inq[y]=1;
                visited[y]++;
            }
               if(visited[y]==n)
            {
                out<<"Ciclu negativ!";
                return 0;
            }
        }

    }
    for(int i=2; i<=n; i++)
    {
        out<<d[i]<<" ";
    }

    return 0;
}