#include <iostream>
#include <vector>

using namespace std;


struct Edges {
    int firstV;
    int secondV;
    int weight;
    Edges(int f, int s, int w) : firstV(f), secondV(s), weight(w) {};
    Edges() :firstV(0), secondV(0), weight(0) {};
};

void initialize(int s, int vertex, vector<int>& result, vector<int>& previous) {
    for (int v = 0; v < vertex; ++v) {
        result[v] = 30000;
        previous[v] = 0;
    }
    result[s] = 0;
}

void relax(Edges e, vector <int>& result, vector <int>& previous) {
    if (result[e.firstV] == 30000)
        return;
    if (result[e.secondV] > result[e.firstV] + e.weight) {
        result[e.secondV] = result[e.firstV] + e.weight;
        previous[e.secondV] = e.firstV;
    }
}

void FordBellman(vector <Edges>& graph, int s, vector <int>& result, int vertex) {
    vector <int> previous(vertex);
    initialize(s, vertex, result, previous);
    for (int i = 0; i < vertex - 1; ++i)
        for (int e = 0; e < graph.size(); ++e)
            relax(graph[e], result, previous);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector <Edges> graph(m);
    vector <int> result(n);
    for (int i = 0; i < m; ++i) {
        int f, s, w;
        cin >> f >> s >> w;
        graph[i] = Edges(f - 1, s - 1, w);
    }
    FordBellman(graph, 0, result, n);
    for (int i = 0; i < n; ++i)
        cout << result[i] << " ";
    //system("pause");
    return 0;
}