#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int N=25e4+1,inf=2e9;
struct elem
{
    int nod,cost;
    bool operator<(const elem &e) const
    {
        return cost<e.cost;
    }
};
int n,m,x,y,c,i,j,d[N],cnt[N];
bool f[N];
queue<int> q;
vector<elem> edge[N];
bool spfa()
{
    d[1]=0;
    q.push(1);
    f[1]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        f[x]=0;
        for(auto e:edge[x])
        {
            y=e.nod;
            c=e.cost;
            if(d[y]>d[x]+c)
            {
                d[y]=d[x]+c;
                if(!f[y])
                {
                    q.push(y);
                    f[y]=1;
                    cnt[y]++;
                    if(cnt[y]>n) return 0;
                }
            }
        }
    }
    return 1;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;++i)
        d[i]=inf;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        edge[x].push_back({y,c});

    }
    if(!spfa())
    {
        fout<<"Ciclu negativ!";
        return 0;
    }
    for(int i=2;i<=n;++i)
        fout<<d[i]<<' ';
    return 0;
}