#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,s;
vector<pair<int,int> > g[N];
int dis[N],book[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
signed main(){
	// step 1、读题、声明变量
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	// step 2、输入
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(make_pair(v,w));
	}
	// step 3、处理
	for(int i=1;i<=n;i++) dis[i]=2147483647;
	dis[s]=0;
	for(int i=0;i<g[s].size();i++){
		dis[g[s][i].first]=min(g[s][i].second,dis[g[s][i].first]);
	}
	q.push(make_pair(0,s));
	while(!q.empty()){
		pair<int,int> now=q.top();
		cout<<q.top().second<<' '<<q.top().first<<'\n';
		q.pop();
		int x=now.second,y=now.first;
		if(book[x]) continue;
		book[x]=1;
		for(int i=0;i<g[x].size();i++){
			int to=g[x][i].first,val=g[x][i].second;
			if(dis[to]>dis[x]+val){
				dis[to]=dis[x]+val;
				if(!book[to]) q.push(make_pair(val,to));
			}
		}
	}
	// step 4、输出
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
	return 0;
}