#include <bits/stdc++.h>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
queue<int> q;
vector<vector<pair<int,int>>> edges;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>  >pq;
int distances[50001];
int counts[50001];
int father[50001];
int main()
{
    int n,m,weight,node1,node2;
    f>>n>>m;
    edges.resize(50001,vector<pair<int,int>>());
    for(int i=1; i<=m; i++)
    {
        f>>node1>>node2>>weight;
        edges[node1].push_back(make_pair(weight,node2));
    }
    for(int i=1; i<=10000; i++)
        distances[i] = INT_MAX - 1;
    distances[1]=0;
    q.push(1);
    pq.push(make_pair(0,1));
    while(!q.empty())
    {
        int currentNode= q.front();
        q.pop();
        for(auto Adj_Weigh: edges[currentNode])
        {
            int weightToNode = Adj_Weigh.first ;
            int adjNode = Adj_Weigh.second;
            if(distances[currentNode] + weightToNode < distances[adjNode])
            {
                distances[adjNode] = distances[currentNode] + weightToNode;
                father[adjNode] = currentNode;
                q.push(adjNode);
                pq.push(make_pair(distances[adjNode],adjNode));
                counts[adjNode]++;
                if(counts[adjNode] == n-1)
                {
                    g<<"Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for(int i=2; i<=n; i++)
        g<<distances[i]<<" ";

}