#include <queue>
#include <vector>
#include <fstream>
using namespace std;
const int oo=1<<28;
const int nmax=50005;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector < pair<int,int> > G[nmax];
queue <int> coada;
int nr_ap[nmax];int dist[nmax];
int n,m;
bool incoada[nmax];
void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        G[x].push_back(make_pair(y,z));
    }
}
void bellmanford(int nod)
{
    coada.push(nod);
    for(int i=1;i<=n;i++)
        dist[i]=oo;
    dist[nod]=0;
    bool nuexistaciclu=0;
    while(!coada.empty())
    {
        int nodcurent=coada.front();
        coada.pop();
        if(nr_ap[nodcurent]==n+1)
        {
            nuexistaciclu=1;
            break;
        }
        for(size_t i=0;i<G[nodcurent].size();i++)
        {
            int vecin=G[nodcurent][i].first;
            int cost=G[nodcurent][i].second;
            if(dist[vecin]>dist[nodcurent]+cost)
            {
                nr_ap[vecin]++;
                dist[vecin]=dist[nodcurent]+cost;
                if(incoada[vecin]==0)
            {
                incoada[vecin]=1;
                coada.push(vecin);
            }
            else incoada[vecin]=0;
            }
        }
    }
    if(nuexistaciclu==1) g<<"Ciclu negativ!";
    else for(int i=1;i<=n;i++)
    {
        if(i!=nod) g<<dist[i]<<" ";
    }
}
int main()
{
citire();
bellmanford(1);
    return 0;
}