#include <bits/stdc++.h>
#define maxN 50005
#define INF (1<<30)
using namespace std;
vector<pair<int,int> >v[maxN];
int n,i,j,m,dist[maxN],x,y,z;
bool viz[maxN];
int cnt[maxN];
queue<int> q;
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d %d %d",&x,&y,&z),
        v[x].push_back(make_pair(y,z));
    q.push(1);
    viz[1]=true;
    for(i=2;i<=n;i++)
        dist[i]=INF;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        viz[x]=false;
        for(vector<pair<int,int> >::iterator it=v[x].begin();it!=v[x].end();it++)
            if(dist[it->first]>dist[x]+it->second)
            {
                dist[it->first]=dist[x]+it->second;
                if(!viz[it->first])
                {
                    cnt[it->first]++;
                    if(cnt[it->first]==n)
                    {
                        printf("Ciclu Negativ!");
                        return 0;
                    }
                    viz[it->first]=true;
                    q.push(it->first);
                }
            }
    }
    for(i=2;i<=n;i++)
        printf("%d ",dist[i]);
    return 0;
}