#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
#define inf 0x7fffffff
using namespace std;

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

bool negative_cycle = false;
int N, M;
vector<int> tata, dist;
vector<pair<int, pair<int, int>>> E;

void bellman_ford(int s){
    dist.resize(N+1, inf);
    tata.resize(N+1, 0);
    dist[s] = 0;

    for (int i = 0; i < N-1; ++i) {
        for (auto edge : E)
            if (dist[edge.second.first] + edge.first < dist[edge.second.second])
                dist[edge.second.second] = dist[edge.second.first] + edge.first;
    }

    for (int i = 0; i < N-1; ++i) {
        for (auto edge : E)
            if (dist[edge.second.first] + edge.first < dist[edge.second.second])
                dist[edge.second.second] = dist[edge.second.first] + edge.first;
    }
}

int main()
{
    in >> N >> M;
    int x, y, c;
    for (int i = 0; i < M; ++i) {
        in >> x >> y >> c;
        E.push_back({c, {x, y}});
    }
    in.close();
    
    bellman_ford(1);

    if(negative_cycle)
        out << "Ciclu negativ!";
    else
        for (int i = 2; i <= N; ++i){
            out << dist[i] << ' ';
        }
    out.close();
    return 0;
}