// BellmanFord cu coada
#include<iostream>
#include<fstream>
#include<limits>
#include<vector>
#include<utility>
#include<deque>

#define pf pop_front
#define pb push_back
#define mkp make_pair
#define DMAX 50003

using namespace std;

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

const int INF=numeric_limits<int>::max();
vector<vector<pair<int,int> > >G(DMAX);
int D[DMAX], ap[DMAX];
int n,m;
bool OKc=false;

void BellmanFord(int start);

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        f>>x>>y>>w;
        G[x].pb(mkp(y,w));
    }
    BellmanFord(1);
    if(!OKc)
        for(int i=2;i<=n;i++)
            if(D[i]==INF)
                g<<0<<" ";
            else
                g<<D[i]<<" ";
    else
        g<<"Ciclu negativ!";
    return 0;
}
void BellmanFord(int start)
{
    for(int i=1;i<=n;i++)
    {
        D[i]=INF;
        ap[i]=0;
    }
    deque<int> q;
    q.pb(start);
    D[start]=0;
    while(!q.empty())
    {
        int nodc=q.front();
        q.pf();
        for(vector<pair<int,int> >::iterator it=G[nodc].begin();it!=G[nodc].end();it++)
            if(D[it->first]>D[nodc]+it->second)
            {
                D[it->first]=D[nodc]+it->second;
                q.pb(it->first);
                ap[it->first]++;
                if(ap[it->first]>n)
                {
                    OKc=true;
                    q.clear();
                }
            }
    }
}