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

#define NMAX 50005
#define inf 0x3f3f3f3f

using namespace std;

vector<pair<int, int> >graf[NMAX];
int N,M;
int d[NMAX],viz[NMAX];
int is_in_q[NMAX];
queue<int> q;


void citire(char fisier[])
{
    ifstream fin(fisier);
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int n1,n2,c;
        fin>>n1>>n2>>c;
        graf[n1].push_back(make_pair(n2,c));
    }

    fin.close();
}

bool bellman_ford(int s)
{
    for(int i=1;i<=N;i++)
    {
        viz[i]=0;
        is_in_q[i]=0;
        d[i]=inf;
    }
    d[s] = 0;
    q.push(s);
    is_in_q[s] = 1;

    while(!q.empty())
    {
        int nod_curent = q.front();
        viz[nod_curent]++;
        if(viz[nod_curent] >= N)
            return false;
        q.pop();
        is_in_q[nod_curent] = 0;

        for(vector<pair<int,int> >::iterator ii = graf[nod_curent].begin();ii!=graf[nod_curent].end();ii++)
        {
            int vecin = ii->first;
            int cost = ii->second;
            if(d[nod_curent]+cost < d[vecin])
            {
                d[vecin] = d[nod_curent]+cost;
                if(!is_in_q[vecin])
                    q.push(vecin);
            }
        }
    }
    return true;
}

int main()
{
    ofstream cout("bellmanford.out");
    citire("bellmanford.in");
    if(bellman_ford(1))
    {
        for(int i=2;i<=N;i++)
            cout<<d[i]<<" ";
    }
    else
        cout<<"Ciclu negativ!";


    return 0;
}