#include<cstdio>
#include<queue>
#include<vector>
#define maxN 50001
#define M 1<<30
using namespace std;
FILE* f=fopen("bellmanford.in","r");
FILE* g=fopen("bellmanford.out","w");
struct nod{
    int inf;
    int c;
};
int cost[maxN],nr[maxN],n,m;
bool viz[maxN];
vector<nod>v[maxN];
queue<int>q;
void citire()
{
    int i,x,y,z;
    nod a;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&z);
        a.inf=y;
        a.c=z;
        v[x].push_back(a);
    }
    for(i=2;i<=n;i++)
        cost[i]=M;
}
int bellman()
{
    int nodcur,nod_cur,i;
    q.push(1);
    nr[1]++;
    while(!q.empty())
    {
        nodcur=q.front();
        q.pop();
        viz[nodcur]=false;
        for(i=0;i<v[nodcur].size();i++)
        {
            if(cost[v[nodcur][i].inf]>cost[nodcur]+v[nodcur][i].c)
            {
                cost[v[nodcur][i].inf]=cost[nodcur]+v[nodcur][i].c;
                nod_cur=v[nodcur][i].inf;
                if(viz[nod_cur]==false)
                {
                    viz[nod_cur]=true;
                    q.push(nod_cur);
                    nr[nod_cur]++;
                    if(nr[nod_cur]>n)
                        return 0;
                }
            }
        }

    }
    return 1;



}
void afisare(int bun)
{
    int i;
    if(bun==0)
        fprintf(g,"Ciclu negativ!");
    else
        for(i=2;i<=n;i++)
        {
            fprintf(g,"%d ",cost[i]);
        }
}
int main()
{
    citire();
    afisare(bellman());
    return 0;
}