#include<iostream>
#include<string>
#include<cmath>
using namespace std;
struct Dis{
    int value;
    bool visit;
    Dis(){
        value = 0;
        visit = false;
    }
};
long long intMax = pow(2,31)-1;
void createGraph(int **arc, Dis *dis, const int edge){
    int start;
    int end;
    int weight;
    int count = 0;
    while(count != edge){
        cin >> start >> end >> weight;
        arc[start-1][end-1] = weight;
        count++;
    }
}

void Dijkstra(int **arc, Dis *dis, const int n,const int begin){
    	//首先初始化我们的dis数组
	for(int i = 0; i< n; i++){
		//设置当前的路径
		dis[i].value = arc[begin-1][i];
	}
	//设置起点到起点的路径为0
	dis[begin-1].value = 0;
	dis[begin-1].visit = true;

	int count = 1;
	//计算剩余的顶点的最短路径（剩余n-1个顶点）
	while(count != n){
		//temp用来保存当前dis数组中最小的那个下标
		//min记录当前的最小值
		int temp = -1;
		int min = intMax;
		for(int i = 0; i < n; i++){
			if(!dis[i].visit&& dis[i].value < min){
				min = dis[i].value;
				temp = i;
			}
		}
		if(temp == -1) break;
		//把temp对应的顶点加入到已经找到的最短路径的集合中
		dis[temp].visit = true;
		++count;
		for(int i = 0; i < n; i++){
			//注意这里的条件arc[temp][i]!=intMax必须加，不然会出现溢出
			if(!dis[i].visit && arc[temp][i]!=intMax && (dis[temp].value+arc[temp][i]) < dis[i].value){
				//如果新得到的边可以影响其他没访问的顶点，那就更新它的最短路径和长度
				dis[i].value = dis[temp].value + arc[temp][i];
			}
		}
	}

}

int main(){
    int n,edge,begin;
    cin >> n >> edge >> begin;
    int **arc = new int*[n];
    for(int i = 0; i < n; i++){
        arc[i] = new int[n];
        for(int k = 0; k < n; k++){
            arc[i][k] = intMax;
        }
    }
    Dis *dis = new Dis[n];

    createGraph(arc,dis,edge);
    Dijkstra(arc,dis,n,begin);

    for(int i = 0; i < n; i++){
        cout << dis[i].value << ' ';
    }

    for(int i = 0; i < n; i++){
        delete[] arc[i];
    }
    delete[] arc;
    delete[] dis;
}