// Readiz lesson: complete C++17 local exercise.
#include <functional>
#include <queue>
#include <vector>
using namespace std;

const long long INF = 4e18;

struct Edge {
    int to;
    long long cost;
};

vector<long long> dijkstra(const vector<vector<Edge>>& graph, int start) {
    int n = (int)graph.size();
    vector<long long> dist(n, INF);
    priority_queue<
        pair<long long, int>,
        vector<pair<long long, int>>,
        greater<pair<long long, int>>
    > pq;

    dist[start] = 0;
    pq.push({0, start});

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

        if (currentDist != dist[u]) {
            continue;
        }

        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            long long nextDist = currentDist + edge.cost;
            if (nextDist < dist[v]) {
                dist[v] = nextDist;
                pq.push({nextDist, v});
            }
        }
    }

    return dist;
}

#include <algorithm>

vector<int> restorePath(int target, const vector<int>& parent) {
    vector<int> path;
    for (int v = target; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}
#include <iostream>
#include <string>
// Parent-tracking variant. The original distance-only function remains above.
pair<vector<long long>, vector<int>> dijkstraWithParents(const vector<vector<Edge>>& graph, int start) {
    vector<long long> dist(graph.size(),INF);
    vector<int> parent(graph.size(),-1);
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
    dist[start]=0; pq.push({0,start});
    while(!pq.empty()) {
        auto [cost,u]=pq.top(); pq.pop();
        if(cost!=dist[u])continue;
        for(const Edge &e:graph[u]) if(cost+e.cost<dist[e.to]) {
            dist[e.to]=cost+e.cost; parent[e.to]=u;
            pq.push({dist[e.to],e.to});
        }
    }
    return {dist,parent};
}
int main(int argc,char **argv) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int target=-1;
    if(argc!=1) {
        if(argc!=3 || string(argv[1])!="--path")return 1;
        try {size_t used; target=stoi(argv[2],&used); if(used!=string(argv[2]).size() || target<0)return 1;} catch(...) {return 1;}
    }
    int n,m,start;
    if(!(cin>>n>>m>>start) || n<1 || n>200000 || m<0 || m>400000 || start<0 || start>=n || target>=n)return 1;
    vector<vector<Edge>> graph(n);
    for(int i=0;i<m;i++) {
        int u,v;long long w;
        if(!(cin>>u>>v>>w) || u<0 || u>=n || v<0 || v>=n || w<0 || w>1000000000)return 1;
        graph[u].push_back({v,w});
    }
    vector<long long> dist; vector<int> parent;
    if(target<0)dist=dijkstra(graph,start);
    else {auto result=dijkstraWithParents(graph,start);dist=std::move(result.first);parent=std::move(result.second);}
    for(int i=0;i<n;i++)cout<<(i?" ":"")<<(dist[i]==INF?-1:dist[i]);
    cout<<'\n';
    if(target>=0) {
        if(dist[target]==INF)cout<<"UNREACHABLE\n";
        else {auto path=restorePath(target,parent);for(int i=0;i<(int)path.size();i++)cout<<(i?" ":"")<<path[i];cout<<'\n';}
    }
}