#include <bits/stdc++.h>
#define nmax 50002
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
class BellmanFord{
vector<pair<int, int> > *v;
int n;
public:
    BellmanFord(int n);
    void add(int x, int y, int cost);
    void drum(int src);
} ;
BellmanFord::BellmanFord(int n)
{
    this->n=n+1;
    v=new vector<pair<int, int> > [n+1];
}
void BellmanFord::add(int x, int y, int cost)
{
    v[x].push_back({y,cost});
}
void BellmanFord::drum(int src)
{
    vector<int> d(n,INF);
    vector<int> viz(n,0);
    queue<int> q;
    int ok=0;
    q.push(src);
    d[src]=0;
    while(q.size())
    {
        int nod=q.front();
        q.pop();
        if(++viz[nod]==n)
        {
            g<<"Ciclu negativ!"<<'\n';
            ok=1;
            break;
        }
        for(int i=0;i<v[nod].size();i++)
            if(d[v[nod][i].first] > d[nod]+v[nod][i].second)
            {
                d[v[nod][i].first] = d[nod]+v[nod][i].second;
                q.push(v[nod][i].first);
            }
    }
    if(!ok)
    {
        for(int i=1;i<n;i++)
        if(i!=src)
        {
            if(d[i]==INF) g<<"0 ";
            else g<<d[i]<<" ";
        }
    }
}
int main()
{
    int n,m,x,y,cost;
    f>>n>>m;
    BellmanFord graf(n);
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        graf.add(x,y,cost);
    }
    graf.drum(1);
    f.close();
    g.close();
    return 0;
}