using namespace std;
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>

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

const int MAX_N=50005;
const int INF=0x3f3f3f3f;

vector < pair <int,int> > adj[MAX_N];
vector <int> adj_t[MAX_N];

int main()
{
    int nodes,edges;
    f>>nodes>>edges;
    for(int i=0; i<edges; ++i)
    {
        int x,y,c;
        f>>x>>y>>c;
        adj[x].push_back(make_pair(y,c));
        adj_t[x].push_back(y);
    }

    queue<int> Q;
    bitset <MAX_N> in_queue(false);
    vector <int> dist(MAX_N,INF), cnt_in_queue(MAX_N,0);
    int negative_cycle=false;

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

    while(!Q.empty() && !negative_cycle)
    {
        int x=Q.front();
        Q.pop();
        in_queue[x]=false;
        vector < pair <int,int> > :: iterator it;
        for(it=adj[x].begin(); it!=adj[x].end(); ++it)
         if(dist[x]<INF) if(dist[it->first]>dist[x]+it->second)
         {
             dist[it->first]=dist[x]+it->second;
             if(!in_queue[it->first])
             {
                 if(cnt_in_queue[it->first]>nodes)
                   negative_cycle=true;
                 else
                 {
                     Q.push(it->first);
                     in_queue[it->first]=true;
                     cnt_in_queue[it->first]++;
                 }
             }
         }
    }

    if(!negative_cycle)
      for(int i=2; i<=nodes; ++i)
        g<<dist[i]<<" ";
    else
      g<<"Ciclu negativ!\n";


    return 0;
}