#include<cstdio>
#include<queue>
#include<vector>
#define M 1<<30
#define maxN 50001
using namespace std;
FILE *f=fopen("bellmanford.in","r");
FILE *g=fopen("bellmanford.out","w");
struct nod{
int inf,c;
};
vector<nod>v[maxN];
queue<int>q;
int n,m,cost[maxN],nr[maxN];
bool viz[maxN];
void citire()
{
    nod a;
    int i,x,y,z;
    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 nod_start)
{
    int nodcur,i,nod_cur;
    q.push(nod_start);
    nr[nod_start]++;
    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 ok)
{
    int i;
    if(ok==0)
        fprintf(g,"Ciclu negativ!");
    else
        for(i=2;i<=n;i++)
            fprintf(g,"%d ",cost[i]);
}
int main()
{
    int ok;
    citire();
    ok=bellman(1);
    afisare(ok);
    return 0;
}