#include<bits/stdc++.h>
#define endl ‘\n’
#define PI 3.14159265358979323844
#define DECIMAL(n) std::cout << std::fixed;std::cout << std::setprecision(n);
#define mp make_pair
#define INT_BITS 64
#define pb push_back
#define M 1000000007
#define int long long int
#define forr(i,a,b) for (int i= a; i <b; ++i)
using namespace std;
signed main(){
int n,m;cin>>n>>m;
vector <pair<int,int> > v[10000];
forr(i,0,m){
int a,b,c;cin>>a>>b>>c;
v[a].pb(mp(b,c));
v[b].pb(mp(a,c));
}
priority_queue <pair<int,int> , vector<pair<int,int> >, greater<pair<int,int> >> Q;
vectordistance(n+1,INT_MAX);
int source;cin>>source;
distance[source]=0;
Q.push(mp(0,source));
while(!Q.empty()){
int d=Q.top().first;
int parent=Q.top().second;
Q.pop();
for(pair<int,int> edge : v[parent]){
if(distance[edge.first] > d+edge.second){
distance[edge.first] = d+edge.second;
Q.push(mp(distance[edge.first],edge.first));
}
}
}
forr(i,0,n)cout<<distance[i]<<" ";}