#include <iostream>
#include <fstream>
#include <queue>
#define nmax 50001
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n,m,drum[nmax],nr,ciclu[nmax];
struct nod
{
    int nr;
    int cost;
    nod *p;
}v[nmax];

queue <nod> q;

void add(int a,int b,int c)
{
    nod *q = new nod;
    q->p = v[a].p;
    q->nr = b;
    q->cost = c;
    v[a].p = q;
}
void read()
{
    f>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        add(a,b,c);
    }
}
bool solve()
{
    int nr;
    for(int i=2;i<=n;i++)drum[i]=999999999;
    for(int i=1;i<=n;i++)v[i].nr = i;
    q.push(v[1]);
    while(!q.empty())
    {
       for(nod *z=q.front().p; z!=NULL; z=z->p)
       {
           if(drum[z->nr] > drum[q.front().nr] + z->cost)
           {
               drum[z->nr] = drum[q.front().nr] + z->cost;
               q.push(v[z->nr]);
               ciclu[z->nr]++;
               if(ciclu[z->nr]>n)
               {
                   cout<<"Ciclu negativ!";
                   return false;
               }
           }
       }
       q.pop();
    }
    return true;
}
void write()
{
    for(int i=2;i<=n;i++)
    {
        if(drum[i]==999999999)g<<0<<" ";
        else g<<drum[i]<<" ";
    }
}
int main()
{
    read();
    if(solve())write();
    return 0;
}