#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50005

using namespace std;

vector<pair<int,int> > g[NMAX];
int n,m,viz[NMAX],cost[NMAX];

void read()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back(make_pair(b,c));
    }
}

void solve()
{
    int k;
    queue<int> q;
    viz[1]=1;
    for(q.push(1);!q.empty();q.pop())
    {
        k=q.front();
        for(vector<pair<int,int> >::iterator it=g[k].begin();it!=g[k].end();++it)
        {
            if(!viz[it->first]||cost[it->first]>cost[k]+it->second)
            {
                ++viz[it->first];
                if(viz[it->first]>=n)
                {
                    printf("Ciclu negativ!\n");
                    return;
                }
                cost[it->first]=cost[k]+it->second;
                q.push(it->first);
            }
        }
    }
    for(int i=2;i<=n;++i)
        printf("%d ",cost[i]);
    printf("\n");
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    read();
    solve();
    return 0;
}