#include<bits/stdc++.h>
#define pb push_back
using namespace std;

const int N = 100001;
const int oo = 1 << 25;

vector<pair<int,int > > g[N];
int n, m, f;
int dist[N];

void Dijkstra(int f){
    priority_queue<pair<int, int>, vector<pair<int,int> >, greater<pair<int, int> > > pq;
    pq.push({0, f});
    fill(dist, dist + n , oo);
    dist[f] = 0;
    while(!pq.empty()){
        cout<<pq.top().first<<"\n\n";
        int u = pq.top().second;
        if(pq.top().first>dist[u]){pq.pop(); continue;} ///optimzizaciq #1
        pq.pop();
        for(auto v : g[u]){
            int  d = v.second;
            int to = v.first;
            if(dist[to] > dist[u] + d){
                dist[to] = dist[u] + d;
                pq.push({dist[to], to});
            }
        }
    }
}

int main(){
    cin >> n>> m;
    for(int i = 0 ; i < m ; ++ i){
        int u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    cin >> f;
    cout << '\n';
    Dijkstra(f);
    for_each(dist, dist + n , [](int i){cout << i << ' ' ;});
    return 0;
}