#include <fstream>
#define inf 1001
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct node
{
    int nr,dist;
    node *next;
} *v[50001];

struct link
{
    int nr;
    link *next;
}*q;

int d[50001],n,m,i,runs,ap[50001]; bool vis[50001];

void create_graph ()
{
    int a,b,di; node *d;
    fin>>a>>b>>di;
    d=new node;
    d->nr=b;
    d->dist=di;
    d->next=v[a];
    v[a]=d;
}

bool bellman_ford ()
{
    int p,x,i; node *l;
    q=new link; link *t,*u;
    q->nr=1; q->next=NULL; u=q;
    for (i=1;i<=n;i++) d[i]=inf;
    d[1]=0;
    while (q!=NULL)
    {
        x=q->nr;
        l=v[x];
        while (l)
        {
            if (d[l->nr]>d[x]+l->dist)
            {
                d[l->nr]=d[x]+l->dist;
                if (vis[l->nr]==0) {t=new link; t->nr=l->nr; t->next=u->next; u->next=t;
                                    vis[l->nr]=1;}
                ap[l->nr]++;
                if (ap[l->nr]==n) return 0;
            }
            l=l->next;
        }
        vis[q->nr]=0; t=q; q=q->next; delete t;
    }
    return 1;
}

int main()
{
    fin>>n>>m;
    for (i=1;i<=m;i++) create_graph ();
    if (!bellman_ford())
    {
        fout<<"Ciclu negativ!";
        return 0;
    }
    else for (i=2;i<=n;i++)
    {
        fout<<d[i]<<" ";
    }
    return 0;
}