#include <fstream>
#define inf 50000001
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
  
struct node
{
    int nr,dist;
    node *next;
} *v[50001];
  
struct queue
{
    int nr;
    queue *next;
}*q;
  
int d[50001],ap[50001],n,m,i; 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 x,i; node *l; bool ok=1;
    q=new queue; queue *t,*u;
    q->nr=1; q->next=NULL; u=q;
    for (i=1;i<=n;i++) d[i]=inf;
    d[1]=0;  ap[1]=1;
    while (q!=NULL)
    {
        ok=0;
        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) {if (ap[l->nr]>n) return 0;
                	                else{ t=new queue; t->nr=l->nr; t->next=NULL; u->next=t; u=t;
                                    vis[l->nr]=1; ap[l->nr]++;}}
            }
            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;
}