#include<fstream>
#include<vector>
#include<queue>
#define NMAX 50005
#define INF 999999
using namespace std;

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

long N,M,d[NMAX],viz[NMAX],cnt[NMAX];

struct muchie{ long x,cst;};
vector<muchie>L[NMAX];

struct comp{
bool operator() (long i,long j)
{
   return d[i]>d[j];
}
};

priority_queue<long,vector<long>,comp> q;

int drum()
{
    d[1]=0;
    q.push(1);
    viz[1]=1;
    long k;

    while(!q.empty())
          {
                k=q.top();
                q.pop();
                viz[k]=0;

                for (unsigned int i=0;i<L[k].size();i++)
                    if (d[L[k][i].x]>d[k]+L[k][i].cst)
                      {d[L[k][i].x]=d[k]+L[k][i].cst;

                      if (viz[L[k][i].x]) continue;
                      cnt[L[k][i].x]++;

                      if (cnt[L[k][i].x]>N) return 0;

                      viz[L[k][i].x]=1;
                      q.push(L[k][i].x);
                      }


          }

return 1;}


int main()
{
    f>>N>>M;
    for (long i=1;i<=M;i++)
    {
        int nod;
        muchie y;

        f>>nod>>y.x>>y.cst;
        L[nod].push_back(y);
    }

    for (int i=1;i<=N;i++)
    d[i]=INF;
    if (!drum())
    g<<"Ciclu negativ!";
    else
    for (long i=2;i<=N;i++)
    g<<d[i]<<" ";

return 0;
}