#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <bitset>
#include <fstream>


using namespace std;

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

    const int maxn = 50005;
    const int inf = 0x3f3f3f3f;

    vector < pair <int, int> > graph[maxn];



int main()
{
    int n,m;

    f>>n>>m;
    for(int i = 0; i<m; i++){
        int from,to,cost;
        f>>from>>to>>cost;
        graph[from].push_back(make_pair(to,cost));
    }
    f.close();
    queue <int> Q;
    bitset <maxn> in_queue(false);
    vector <int> dist(maxn,inf), cnt_inque(maxn,0);
    bool cycle_neg = false;

    dist[1] = 0;
    Q.push(1);
    in_queue[1].flip();

    while(!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        in_queue[p] = false;
        vector <pair<int, int> >:: iterator it;
        for(it = graph[p].begin();it!=graph[p].end();++it)
        {
            int fiu,cost;
            fiu = it->first;
            cost = it->second;
           if( dist[fiu] > cost + dist[p] )
           {
               dist[fiu] = cost + dist[p];
               if(!in_queue[fiu])
               {
                   if(cnt_inque[fiu] > n)
                   {
                       cycle_neg = true;
                   }

                   else{
                    Q.push(fiu);
                    in_queue[fiu] = true;
                    cnt_inque[fiu]++;
                   }
                }
            }
        }
    }

   if(!cycle_neg){
    for(int i = 2; i <=n;i++)
        g<<dist[i]<<" ";
   }
    else g<<"Ciclu negativ!\n";
    g.close();


    return 0;
}