#include <fstream>
#include <vector>
#include <deque>
#define MAX 500
#define inf 1000
#define pb push_back

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct nod {int y, c;};

vector <nod> V[ MAX ];

deque <int> QUEUE;
void citire();
int BellmanFord();
void afisare();

int n, m, dist[ MAX ], c, nr[ MAX ];

int main()
{
    citire();
    afisare();
    return (0);
}

void citire()
{ int i;
     fin>>n>>m;
     int x, c;
     nod t;
     for(i=1; i<=m; i++)
        {
         fin>>x>>t.y>>t.c;
         V[x].pb(t);
     }

     fin.close();
};

int BellmanFord()
{ int i,y;
    for(i=2; i<=n; i++)
        dist[i]=inf;
    dist[1]=0;
    QUEUE.pb(1);
    while(!QUEUE.empty() )
        {
            int x=QUEUE.front();
            if( dist[x]!=inf ) {
                 for(i=0; i < V[x].size(); i++)
                    {
                     y=V[x][i].y,
                     c=V[x][i].c;
                         if(dist[y]>dist[x]+c)
                            {
                            dist[y]=dist[x]+c;
                             QUEUE.pb(y);
                             if(++nr[y]>n-1)
                                return 0;
                        }
                 }
            }
            QUEUE.pop_front();
    }
return 1;
}

void afisare()
{ int i;
    if( BellmanFord())
        {
        for(i=2; i<=n; i++)
           fout<<dist[i]<<" ";
        }
    else
         fout<<"Ciclu negativ!";
}