#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int ap[50001],cst[50001],n,m,i,x,y,z,nd,cnt[50001];
queue  < int > q;
vector < int > v[50001];
vector < int > val[50001];
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(y);
        val[x].push_back(z);
    }
    for(i=1;i<=n;i++) cst[i]=INF;
    q.push(1);
    cst[1]=0;
    ap[1]=1;
    while(!q.empty())
    {
        nd=q.front();
        q.pop();
        ap[nd]=0;
        for(i=0;i<v[nd].size();i++)
            if(cst[nd]+val[nd][i]<cst[v[nd][i]])
            {
                cst[v[nd][i]]=cst[nd]+val[nd][i];
                if(!ap[v[nd][i]])
                {
                    q.push(v[nd][i]);
                    ap[v[nd][i]]=1;
                    if(++cnt[v[nd][i]]>n)
                    {
                        printf("Ciclu negativ!");
                        return 0;
                    }
                }
            }
    }
    for(i=2;i<=n;i++)
        printf("%d ",cst[i]);
    return 0;
}