#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;
set<pair<int, int>> st;
for (int i = 0; i < n; i++) {
st.insert({w[i], i});
}
while (!st.empty()) {
pair<int, int> cur_pair = *st.begin();
st.erase(cur_pair);
int cur_rst = cur_pair.first;
int cur = cur_pair.second;
for (auto e : g[cur]) {
int nxt = e.first;
int cur_nxt_w = e.second;
if (w[nxt] > w[cur] + cur_nxt_w) {
st.erase({w[nxt], nxt});
w[nxt] = w[cur] + cur_nxt_w;
st.insert({w[nxt], nxt});
}
}
}
for (auto e : w) cout << e << ' ';
return 0;
}