#include <iostream>
#include <climits>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4; // 防止加法溢出

/*
 * Dijkstra 单源最短路（适用于边权非负的图）
 *
 * 图的表示：邻接表 vector<vector<pair<int, ll>>> adj;
 * 每个 pair : (to, weight)
 *
 * 返回值：
 *   dist - 长度为 n 的数组，dist[v] 为 s 到 v 的最短距离（若不可达为 INF）
 *   prev - 长度为 n 的数组，prev[v] 为路径上 v 的前驱，若 prev[v] == -1 表示无前驱
 *
 * 复杂度：O((n + m) log n)
 */

pair<vector<ll>, vector<int>> dijkstra(int n, const vector<vector<pair<int,ll>>> &adj, int s) {
    vector<ll> dist(n, INF);
    vector<int> prev(n, -1);           // 用于重建路径
    dist[s] = 0;

    // min-heap : pair(dist, node)
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        // 延迟删除：若堆中条目的距离已经过时（大于当前 dist[u]），忽略它
        if (d != dist[u]) continue;

        // 遍历邻接边
        for (auto &edge : adj[u]) {
            int v = edge.first;
            ll w = edge.second;

            // 松弛操作
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    return {dist, prev};
}

/*
 * 辅助：从 prev 数组重建 s -> t 的路径（若不可达返回空向量）
 */
vector<int> reconstruct_path(int s, int t, const vector<int> &prev) {
    vector<int> path;
    if (prev[t] == -1 && s != t) {
        // 若 t 未被访问（且不是源点本身），返回空
        return path;
    }
    for (int cur = t; cur != -1; cur = prev[cur]) {
        path.push_back(cur);
    }
    reverse(path.begin(), path.end());
    // 若起点不是 s，则说明 t 不可达，返回空
    if (!path.empty() && path.front() == s) return path;
    return vector<int>();
}

// 示例主函数（输入输出示范）
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    // 输入顶点数 n，边数 m
    if (!(cin >> n >> m)) return 0;

    vector<vector<pair<int,ll>>> adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        // 假设输入为 0-index；若是 1-index，请在读取后减 1
        adj[u].push_back({v, w});
        // 若是无向图，也要添加反向边：
        // adj[v].push_back({u, w});
    }

    int s;
    cin >> s; // 起点

    auto [dist, prev] = dijkstra(n, adj, s);

    // 输出每个点的最短距离
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INF) cout << "INF";
        else cout << dist[i];
        if (i + 1 < n) cout << ' ';
    }
    cout << '\n';

    // 示例：重建并输出从 s 到 t 的路径
    int t;
    if (cin >> t) {
        auto path = reconstruct_path(s, t, prev);
        if (path.empty()) {
            cout << "No path from " << s << " to " << t << '\n';
        } else {
            for (int x : path) cout << x << ' ';
            cout << '\n';
        }
    }

    return 0;
}