#include <cstdio>
#include <vector>
#include <queue>
#define verticesMax 51024
#define intmax 51048576

using namespace std;

class Arc {
public:
    int to,cost;

    Arc();
    Arc(int newTo,int newCost);
};

Arc::Arc() {
}

Arc::Arc(int newTo,int newCost) {
    to=newTo;
    cost=newCost;
}

int vertices;
vector <Arc> Graph[verticesMax];
int costs[verticesMax],viz[verticesMax];
queue <int> JustMarried,WillingToMarry;

void readArc() {
    int newFrom,newTo,newCost;
    scanf("%d%d%d",&newFrom,&newTo,&newCost);
    Arc NewArc(newTo-1,newCost);
    Graph[newFrom-1].push_back(NewArc);
}

void setCosts() {
    int i;
    for(i=0;i<vertices;++i) {
        costs[i]=intmax;
    }
}

void read() {
    int i,arcs;
    scanf("%d%d",&vertices,&arcs);
    for(i=0;i<arcs;++i) {
        readArc();
    }
    setCosts();
}

void goThrough(int from) {
    for(auto&UArc:Graph[from]) {
        if(costs[UArc.to]>costs[from]+UArc.cost) {
            costs[UArc.to]=costs[from]+UArc.cost;
            if(!viz[UArc.to]) {
                WillingToMarry.push(UArc.to);
            }
            ++viz[UArc.to];
        }
    }
}

void qCopy() {
    int cpy;
    for(;!WillingToMarry.empty();WillingToMarry.pop()) {
        cpy=WillingToMarry.front();
        JustMarried.push(cpy);
    }
}

void advance() {
    int cpy;
    for(;!JustMarried.empty();JustMarried.pop()) {
        cpy=JustMarried.front();
        goThrough(cpy);
    }
    qCopy();
}

void solve() {
    int i;
    costs[0]=0;
    JustMarried.push(0);
    for(i=1;i<vertices;++i) {
        advance();
    }
}

void show() {
    int i;
    for(i=1;i<vertices;++i) {
        printf("%d ",costs[i]);
    }
}

void error() {
    printf("Ciclu negativ!");
}

void display() {
    advance();
    if(JustMarried.empty()) {
        show();
    }
    else {
        error();
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    read();
    solve();
    display();
    return 0;
}