#include<fstream>
#include<vector>
#include<cstring>
#include<queue>

#define NMAX 50001
#define INF 100000001

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

struct Edge {
    int n, c;
    Edge(int a, int b) {
        n = a; c = b;
    }
};

int COST[NMAX];
bool INQ[NMAX];
vector<Edge> G[NMAX];
queue<int> Q;
int n;

void citire() {
    int m, a, b, c;
    fin>>n>>m;
    while(m--) {
        fin>>a>>b>>c;
        G[a].push_back(Edge(b, c));
    }
}

bool bellman(const int &start) {
    int pas, node;
    Q.push(start);
    memset(COST, INF, sizeof(COST));
    INQ[start] = 1;
    COST[start] = 0;
    while(!Q.empty() && pas < n*n) {
        node = Q.front();
        Q.pop();
        INQ[node] = 0;
        for(vector<Edge>::iterator it = G[node].begin(); it!=G[node].end(); ++it) {
            if(COST[(*it).n] > COST[node] + (*it).c) {
                COST[(*it).n] = COST[node] + (*it).c;
                if(!INQ[(*it).n]) {
                    INQ[(*it).n] = 1;
                    Q.push((*it).n);
                }
            }
        }
    }
    if(!Q.empty()) {
        fout<<"Ciclu negativ!";
        return false;
    }
    return true;
}

void afisare() {
    for(int i=2; i<=n; i++) {
        fout<<COST[i]<<" ";
    }
}

int main() {
    citire();
    if(bellman(1))
        afisare();
}