#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <climits>
#include <queue>
using namespace std;
int V,E,dist[50010];
vector <pair <int,int> > adj[50010];
int nr[50010];

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

int bellmanford()
{
    queue <int> q;
    q.push(1);

    for(int i=1;i<=V;i++)
        dist[i]=INT_MAX;
    dist[1]=0;

    int vertex;
    while(!q.empty() )
    {
        vertex=q.front();
        q.pop();
        for(vector<pair<int,int> >::iterator it=adj[vertex].begin();it!=adj[vertex].end();it++)
        {

            if(dist[it->second]>dist[vertex]+it->first)
            {
                if(nr[it->second]>=V)
                {
                    g << "Ciclu negativ!";
                    return 0;
                }

                dist[it->second]=dist[vertex]+it->first;
                q.push(it->second);
                nr[it->second]++;

            }
        }

    }

    return 1;

}


int main()
{


    f >> V >> E;
    int x,y,cost;
    for(int i=0;i<E;i++)
    {
        f >> x >> y >> cost;
        adj[x].push_back(make_pair(cost,y));
    }

    if( bellmanford()==true)
    {
        for(int i=2;i<=V;i++){

        g << dist[i] << " ";

        }
    }


    return 0;
}