#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
bool viz[50001];
int v[50001],nrq[50001],n;
struct muchie
{
    int x;
    int c;
};
vector<muchie> l[50001];




void bfs(int u)
{
    queue<int> q;
    vector<muchie>::iterator it;
    q.push(u);
    viz[u]=1;
    ++nrq[u];
    while(!q.empty())
    {
        u=q.front();
        viz[u] = false;
        for(it=l[u].begin();it!=l[u].end();++it)
        {
            if(v[u] + it->c < v[it->x]||v[it->x]==0)
            {
                v[it->x] = v[u] + it->c;
                if(!viz[it->x])
                {
                    if(nrq[it->x]<n)
                        q.push(it->x);
                    ++nrq[it->x];
                    viz[it->x] = true;
                }
            }
        }
        q.pop();
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int i,m,x;
    muchie p;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&p.x,&p.c);
        l[x].push_back(p);
    }
    bfs(1);
    if(v[1]<=0)
        printf("Ciclu negativ!");
    else
        for(i=2;i<=n;++i)
            printf("%d ",v[i]);
    return 0;
}