#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;

const int INF = 1 << 30;

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


class Graph {
private:
    int _n, _m;
    vector<vector<int>> _list;
    vector<vector<pair<int, int> >> _list2;

    int viz[100001] = {0};

public:
    Graph(int nodes, int edges) : _n(nodes), _m(edges) {}

    void addEdges();

    void addEdges_Oriented();

    void add();

    void bellmanford(int s);
};

void Graph::addEdges() {
    int x, y, i;
    for (i = 0; i < _m; ++i) {
        f >> x >> y;
        _list[x].push_back(y);
        _list[y].push_back(x);
    }
}

void Graph::addEdges_Oriented() {
    int x, y, i;
    for (i = 0; i < _m; ++i) {
        f >> x >> y;
        _list[x].push_back(y);
    }
}

void Graph::add() {
    int x, y, c;
    _list2.resize(_n + 1);

    for (int i = 0; i < _m; ++i) {
        f >> x >> y >> c;
        _list2[x].push_back(make_pair(y, c));
    }
}

void Graph::bellmanford(int start) {
    vector<int> dist(_n + 1, INF);
    queue<int> q;  // optimizare folosind coada
    vector<int> inQueue(_n + 1, 0);
    dist[start] = 0;
    q.push(start);
    inQueue[start] = 1;

    while (!q.empty()) {
        int currentNode = q.front();
        q.pop();
        viz[currentNode] += 1; // numar de cate ori a fost vizitat un nod pentru a detecta ciclurile
        inQueue[currentNode] = 0;

        if (viz[currentNode] >= _n) {
            g << "Ciclu negativ!";
            return;
        }


        for (int i = 0; i < _list2[currentNode].size(); ++i) {
            int neighbour = _list2[currentNode][i].first;
            int cost = _list2[currentNode][i].second;

            if (dist[neighbour] > dist[currentNode] + cost) {
                dist[neighbour] = dist[currentNode] + cost;
                if (inQueue[neighbour] == 0) q.push(neighbour);
            }
        }

    }

    for (int i = 2; i <= _n; ++i)
        g << dist[i] << " ";

}


int main() {
    int n, m;
    f >> n >> m;
    Graph gr(n, m);
    gr.add();

    gr.bellmanford(1);

    f.close();
    g.close();
    return 0;
}