#include<fstream>
#include<queue>
#include<vector>
#include<cstdlib>
using namespace std;

typedef pair<int,int> per;
typedef vector<per>::iterator it;
#define x first
#define y second
#define BM 50005

int n,m,d[BM],inq[BM],nt[BM];
vector<per>gr[BM];
queue<int> c;

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

void bf(){
    it i;
    int fr;
    c.push(1);
    inq[1]=1;
    for(;!c.empty();c.pop()){
        fr=c.front();
        for(i=gr[fr].begin();i!=gr[fr].end();++i){
            if(d[i->x]>d[fr]+(i->y)){
                d[i->x]=d[fr]+(i->y);
                ++nt[i->x];
                if(nt[i->x]>=n){
                    g<<"Ciclu negativ!";
                    exit(0);
                }
                if(inq[i->x]==0)c.push(i->x),inq[i->x]=1;
            }
        }
        inq[fr]=0;
    }
}

int main (){
    int i,a,b,c;
    f>>n>>m;
    for(i=1;i<=m;++i){
        f>>a>>b>>c;
        gr[a].push_back(make_pair(b,c));
    }
    d[1]=0;
    for(i=2;i<=n;++i)d[i]=(1<<30);
    bf();
    for(i=2;i<=n;++i)g<<d[i]<<' ';
    return 0;
}