//BELLMAN FORD
#include<iostream>
#include<fstream>
#include<vector>
#include<limits>

#define pb push_back
#define DMAX 50005
using namespace std;

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

struct triplet{
    int p;
    int d;
    int c;
};

const int INF=numeric_limits<int>::max()/2;
vector<triplet> E;
int D[DMAX];

int n,m;
bool OKc=true;
void BellmanFord(int start);

triplet mkt(int x,int y,int w);
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int p,d,c;
        f>>p>>d>>c;
        E.pb(mkt(p,d,c));
    }
    BellmanFord(1);
    if(OKc==true)
        for(int i=2;i<=n;i++)
            g<<D[i]<<" ";
    else
        g<<"Ciclu negativ!";
    return 0;
}

void BellmanFord(int start)
{
    for(int i=1;i<=n;i++)
        D[i]=INF;
    D[start]=0;
    for(int i=1;i<n;i++)
        for(vector<triplet>::iterator it=E.begin();it!=E.end();it++)
            if(D[it->d]>D[it->p]+it->c) D[it->d]=D[it->p]+it->c;
    for(vector<triplet>::iterator it=E.begin();it!=E.end();it++)
            if(D[it->d]>D[it->p]+it->c) OKc=false;
}
triplet mkt(int x, int y, int w)
{
    triplet t;
    t.p=x;
    t.d=y;
    t.c=w;

    return t;
}