#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];

int q[100001],d[50001],n,m,i,runs; 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,u,x,i; p=u=1; node *l;
    q[1]=1;
    for (i=1;i<=n;i++) d[i]=inf;
    d[1]=0;
    while (p<=u&&runs<=m*(n-1))
    {
        x=q[p];
        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) {q[++u]=l->nr;
                                    vis[l->nr]=1;}
            }
            l=l->next;
            runs++;
        }
        vis[q[p]]=0; p++;
    }
    if (runs>(n-1)*m) return 0;
    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;
}