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

#define MAX_N 50000

std::vector<std::pair<int, int>> outgoing[MAX_N+1];
std::queue<int> node_queue;
int visit_count[MAX_N+1];
int dist[MAX_N+1];
bool in_queue[MAX_N+1];

int main() {
    int n, m;
    std::ifstream fin("bellmanford.in");
    fin >> n >> m;
    for(int i=0; i<m; i++) {
        int a, b, c;
        fin >> a >> b >> c;

        outgoing[a].push_back({b, c});
    }
    fin.close();

    for(int i=2; i<=n; i++) dist[i] = 999999999;

    dist[1] = 0;
    node_queue.push(1);
    in_queue[1] = true;

    while(!node_queue.empty()) {
        int nod = node_queue.front(); node_queue.pop();

        visit_count[nod]++;
        in_queue[nod] = false;
        if(visit_count[nod] >= n) {
            std::ofstream fout("bellmanford.out");
            fout << "Ciclu negativ!" << std::endl;
            fout.close();
            return 0;
        }

        for(auto edge : outgoing[nod]) {
            int to_where = edge.first, cost = edge.second;

            if(dist[to_where] > dist[nod] + cost) {
                dist[to_where] = dist[nod] + cost;
                if(!in_queue[to_where]) {
                    node_queue.push(to_where);
                    in_queue[to_where] = true;
                }
            }
        }
    }

    std::ofstream fout("bellmanford.out");
    for(int i=2; i<=n; i++) fout << dist[i] << " ";
    fout << std::endl;
    fout.close();

    return 0;
}