#include <fstream>
#include <queue>
#include <vector>
#define x first
#define y second
#define inf 2000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
queue<int > q;
pair<int,int> nxt;
int f[50010],i,j,n,m,c[50010],now;
vector <pair<int,int> > v[50010];
int main()
{
    fin>>n;
    fin>>m;
    for(i=1;i<=m;i++)
    {
        int a,b,cost;
        fin>>a>>b>>cost;
        v[a].push_back(make_pair(b,cost));
    }
    for(i=2;i<=n;i++)
        c[i]=inf;
    q.push(1);
    while(!q.empty())
    {
        now=q.front();
        f[now]++;
        if(f[now]>=n)
        {
            fout<<"Ciclu negativ!";return 0;
        }
        for(i=0;i<v[now].size();i++)
            if(c[v[now][i].x]>c[now]+v[now][i].y)
                c[v[now][i].x]=c[now]+v[now][i].y,q.push(v[now][i].x);
        q.pop();
    }
    for(i=2;i<=n;i++)
        fout<<c[i]<<" ";
    return 0;
    return 0;
}