#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int inf=20010318;
int n,m,v; 
int x,y,z;
int g[101][101];
int f[101][101],path[101],p[101],d[101];
vector<int>haha[101];
queue<int>q;
bool pp=0;
//inline void find(int cur)
//{
//    if(cur==v)
//    {
//        printf("%d ",cur);
//    }
//    else
//    {
//        find(path[cur]);
//        printf("%d ",cur);
//    }
//    return;
//}
inline void dfs(int l,int r,int deep){
	//cout<<l<<" "<<r<<endl;
    if(l==r){
    	//cout<<endl;
    	//int t=p,tot=0;
		//for(int i=1;i<deep;i++){
		//	tot+=f[t][path[i]];
		//	t=path[i];
		//}
    	//if(tot==f[p][r]){
    	cout<<v<<" ";
    	   for(int i=1;i<deep;i++)
    		cout<<path[i]<<" ";	
    		pp=1;
		//}
    	//cout<<endl;
    	//cout<<"aaaaaaaaaaaaaaaa\n";
    	
		return ;
	}
	for(int i=0;i<n;i++)
    if(!pp&&g[l][i]==f[l][i]&&i!=l&&f[l][i]+f[i][r]==f[l][r]){
    	//cout<<deep<<":"<<i<<"->";
		path[deep]=i;
		dfs(i,r,deep+1);
	}
	return ;
}
 
inline void read()
{
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	scanf("%d%d%d",&n,&m,&v);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		f[i][j]=inf;
	for(int i=0;i<n;i++)
		f[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		f[x][y]=z;
		g[x][y]=z;
	}
	for(int k=0;k<n;k++)
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
			{
				if(f[i][j]>f[i][k]+f[k][j])
				{
					f[i][j]=f[i][k]+f[k][j];
				}
			}
	for(int i=0;i<n;i++)
	{
		printf("%d",i);
		printf(":\n");
		if(f[v][i]==0)printf("no\n");
		else if(f[v][i]==inf)printf("no\n");
		else
		{
			printf("path:");
			pp=0;
			//cout<<v<<" ";
			dfs(v,i,1);
			printf("\n");
			printf("cost:");
			printf("%d\n",f[v][i]);
		}
	}
}
int main()
{
	read();
	return 0; 
}