#include <iostream>
#include <set>
#include <vector>
#include <deque>
#include <map>
#include <cmath>
#include <random>

#define se second
#define fi first
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef long double ld;

using namespace std;

const int inf = (int)1e9;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y, W;
        cin >> x >> y >> W;
        x--, y--;
        g[x].push_back(make_pair(y, W));
        g[y].push_back(make_pair(x, W));
    }
    int start;
    cin >> start;
    start--;
    vector<int> w(n, inf);
    w[start] = 0;
    vector<bool> used(n, false);
    for (int _ = 0; _ < n; _++) {
        int cur_rst = inf + 1;
        int cur = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i] && w[i] < cur_rst) {
                cur_rst = w[i];
                cur = i;
            }
        }
        for (auto e : g[cur]) {
            int nxt = e.first;
            int cur_nxt_w = e.second;
            if (w[nxt] > w[cur] + cur_nxt_w) {
                w[nxt] = w[cur] + cur_nxt_w;
            }
        }
    }
    for (auto e : w) cout << e << ' ';
    return 0;
}