#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct edge{
	int to,next,s,from;
}e[100005];
int head[105],tot;
int n,m,st;
int dis[105],fa[105];
bool inq[105];
queue<int> q;
void add(int u,int v,int s){
	e[++tot].to=v;
	e[tot].next=head[u];
	e[tot].s=s;
	e[tot].from=u;
	head[u]=tot;
}
void SPFA(){
	memset(dis,127,sizeof(dis));
	dis[st]=0;
	q.push(st);
	inq[st]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int v,c=head[u];c;c=e[c].next){
			v=e[c].to;
			if(dis[v]>=dis[u]+e[c].s){
				fa[v]=c;
				dis[v]=dis[u]+e[c].s;
				if(!inq[v]){q.push(v),inq[v]=1;}
			}
		}
		inq[u]=0;
	}
}
int main(){
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	scanf("%d%d%d",&n,&m,&st);
	for(int u,v,s,i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&s);
		add(u,v,s); 
	} 
	SPFA();
	for(int i=0;i<n;i++){
		printf("%d:\n",i);
		if(dis[i]>=1e9+7)printf("no\n");
		else if(i==st)printf("no\n");
		else{
			printf("path:");
			int ans[105],top=0;
			for(int j=fa[i];;j=fa[e[j].from]){
				ans[++top]=e[j].to;
				if(e[j].from==st)break;
			}
			printf("%d",st);
			for(int j=top;j>0;j--){
				printf(" %d",ans[j]);
			}
			printf("\ncost:%d\n",dis[i]);
		}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}