#include<vector>
#include<queue>
#include<fstream>
#define oo 1e9
using namespace std;
vector<pair<int,int>>L[60001];
vector<long long>d;
int n,m;
void citire()
{
    ifstream f("bellmanford.in");
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        L[x].push_back({y,c});

    }
    f.close();
}
vector<int> cnt;
vector<bool> inq;
void Bellman_Ford(int p,bool &ngcl)
{
    d.resize(n+1,oo);
    cnt.resize(n+1,0);
    inq.resize(n+1,0);
    d[p]=0;
    queue<int> q;
    q.push(p);
    inq[p]=true;
    cnt[p]=1;
    while(!q.empty())
    {
        int k;
        k=q.front();
        q.pop();
        inq[k]=true;
        for(auto e:L[k])
        {
            int i,c;
            i=e.first;
            c=e.second;
            if(d[k]+c<d[i])
            {
                d[i]=d[k]+c;
                if(!inq[i])
                {
                    q.push(i);
                    inq[i]=false;
                    cnt[i]++;
                    if(cnt[i]>n)
                    {
                        ngcl=true;
                        return;
                    }
                }
            }
        }
    }

}
int main()
{
    citire();

    bool ngcl=false;
    Bellman_Ford(1,ngcl);
    ofstream g("bellmanford.out");
    if(ngcl==true)
    {
        g<<"Ciclu negativ";
    }
    else
    {
        for(int i=2;i<=n;i++)
          if(d[i]!=oo)
            g<<d[i]<<" ";
            else continue;

    }
    g.close();
    return 0;
}