#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];

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

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

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

    int vertex,Repeated=1;

    while(!q.empty() && Repeated <=V+1)
    {
        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)
            {

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

        }

        Repeated++;
    }



    return Repeated <= V+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] << " ";

        }
    }
    else g  <<  "Ciclu negativ!";

    return 0;
}