#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair<int,int>>lista[100005];
void citire(int &n,int &m,int &p)
{
    int x,y,cost;
    fin>>n>>m>>p;
    for(int i=0;i<m;i++){
        fin>>x>>y>>cost;
        lista[x].push_back({y,cost});
        lista[y].push_back({x,cost});
    }
}
int dp[100005];
void bellman_ford()
{
    int n,m,p;
    citire(n,m,p);
    queue<int>q;
    for(int i=0;i<=n;i++)
        dp[i]=-1;
    dp[p]=0;
    q.push(p);
    while(!q.empty())
    {
      int x=q.front();
      q.pop();
      for(auto i:lista[x])
      {
          int cost=dp[x]+i.second;
          if(dp[i.first]==-1 || dp[i.first]>cost)
          {
              dp[i.first]=cost;
              q.push(i.first);
          }
        }
    }
    for(int i=1;i<=n;i++)
        fout<<dp[i]<<" ";
}
int main()
{
    bellman_ford();
    return 0;
}