#include <bits/stdc++.h>
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

void D(int N, vector<pair<int,int>> adj[N]; int source){
    vector<int> dist(V,1000000);
    dist[source] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>>> pq;
    pq.push({0,source});
    
    while(pq.empty() != 0) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        
        for(int i = 0; i < adj[u].size(); i++){
            int v = adj[u][i].first;
            int weight = adj[u][i].second;
            
            if(dist[adj[u][i].first] > pq.top().first + adj[u][i].second){
                dist[adj[u][i].first] = pq.top().first + adj[u][i].second;
                pq.push({dist[adj[u][i].first], adj[u][i].first});
            }
    }
}


int main(){
    int N,M; //số đỉnh, cạnh
    cin >> N >> M;
    
    vector<pair<int,int>> adj;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c}); // Nếu đồ thị là vô hướng
        adj[b].push_back({a,c});
    }
    
    int source;
    cin >> source;
    D(N, adj, source);
    return 0;
    
}