#include <bits/stdc++.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define INF INT_MAX

const int NMAX = 50001;
vector< pair<int,int> > adjList[NMAX];
int dist[NMAX];
int used[NMAX];
queue<int> q;

bool isNegative;

void BellmanFord(int source,int n)
{
    for(int i=0; i<=n; i++)
    {
        dist[i] = INF;
    }

    q.push(source);
    dist[source] = 0;
    while(!q.empty() && !isNegative)
    {
        int curNode = q.front();
        q.pop();
        used[curNode] = false;

        for(int i=0; i<adjList[curNode].size(); i++)
        {
            if(adjList[curNode][i].second + dist[curNode] < dist[adjList[curNode][i].first])
            {
                dist[adjList[curNode][i].first] = adjList[curNode][i].second + dist[curNode];

                if(!used[adjList[curNode][i].first])
                {
                    q.push(adjList[curNode][i].first);
                    used[adjList[curNode][i].first] = true;
                }
            }
        }

        for(int i=0; i<adjList[curNode].size(), isNegative; i++)
        {
            if(adjList[curNode][i].second + dist[curNode] < dist[adjList[curNode][i].first])
            {
                isNegative = true;
            }
        }
    }
}


int main()
{
    int n,m,x,y,cost;
    f>>n>>m;
    for(int i=0; i<m; i++)
    {
        f>>x>>y>>cost;
        adjList[x].push_back(make_pair(y,cost));
    }
    isNegative = false;
    BellmanFord(1,n);
    if(isNegative)
    {
        g<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2;i<=n;i++)
            g<<dist[i]<<" ";
    }
        return 0;
}