#include <fstream>
#include <vector>
#include <queue>
#define nod first
#define cost second
#define msj "Ciclu negativ!"
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
const int lim=5e4+3;
const int inf=1e9+7;
vector<pair<int,int> > vec[lim];
int dist[lim];
bool inq[lim];
int cnt[lim];
queue<int> q;
int n,m,a,b,c;
void bellman()
{
    for(int i=2;i<=n;++i)
        dist[i]=inf;
    dist[1]=0;
    inq[1]=true;
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();
        inq[x]=false;
        q.pop();
        for(auto t:vec[x])
        if(dist[t.nod]>dist[x]+t.cost)
        {
            cnt[t.nod]=cnt[x]+1;
            if(cnt[t.nod]>=n)
            {
                cout<<msj<<'\n';
                exit(EXIT_SUCCESS);
            }
            dist[t.nod]=dist[x]+t.cost;
            if(!inq[t.nod])
            {
                inq[t.nod]=true;
                q.push(t.nod);
            }
        }
    }
    for(int i=2;i<=n;++i)
        cout<<dist[i]<<' ';
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        vec[a].push_back({b,c});
    }
    bellman();
    return 0;
}