#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

bool Check_Negative ();

unsigned int N, M;
unsigned int x[250001], y[250001];
int c[250001];

vector <unsigned int> G[50001];
vector < pair <int, unsigned int> > H;
pair <int, unsigned int> PR;
bool seen[50001];
unsigned long long int step;
unsigned int pos, node;
unsigned int i, j;

int cost[50001];

int main ()
{
    /// READ
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x[i] >> y[i] >> c[i];
        G[x[i]].push_back(i);                   /// Store position of node x.
    }

    /// INITIALIZE
    for (i=2; i<=N; i++)                        /// Initialize solution with big values.
        cost[i] = INT_MAX;
    H.push_back(make_pair(0,1));                /// Initialize heap.
    make_heap(H.begin(),H.end());

    /// SOLVE
    while (H.size()!=0 && step<=1LL*N*M)           /// While the heap is not empty and we didn't make enough steps...
    {
        step++;                                                     /// Count steps.
        pop_heap(H.begin(),H.end());                                /// Delete heap.
        PR = H.back();                                              /// Select a part of the heap to use.
        H.pop_back();
        node = PR.second;                                           /// Select node.
        seen[node] = 0;                                             /// Mark it as seen.
        for (j=0; j<G[node].size(); j++)                            /// Go through nodes.
        {
            pos = G[node][j];                                       /// Select current position.
            if (cost[x[pos]]+c[pos] < cost[y[pos]])                 /// If we can update the solution...
            {
                cost[y[pos]] = cost[x[pos]] + c[pos];               /// Update solution.
                if (!seen[y[pos]])                                  /// If node y of pos was not seen...
                {
                    seen[y[pos]] = 1;                               /// We mark it as seen.
                    H.push_back(make_pair(-cost[y[pos]],y[pos]));   /// Update heap.
                    push_heap(H.begin(),H.end());
                }
            }
        }
    }

    /// PRINT
    if (Check_Negative() == 1)          /// If we have a negative cycle...
        fout << "Ciclu negativ!";       /// Print that.
    else                                /// Else
        for (i=2; i<=N; i++)            /// Print the solution.
            fout << cost[i] << ' ';
    return 0;
}

bool Check_Negative ()                      /// Check if we have at least one negative cycle or not.
{
    for (i=1; i<=M; i++)
        if (cost[x[i]]+c[i] < cost[y[i]])   /// If we have a negative cycle...
            return 1;                       /// Return 1 and stop.
    return 0;                               /// We don't have a negative cycle.
}