#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define R register
#define ll long long
#define N 105
#define inf 707406378
#define no printf("no")
#define path printf("path:")
#define cost printf("cost:")
#define mod 1000000007

inline void in(int &x) {
    static int ch; static bool flag;
    for(flag = false,ch = getchar();ch < '0'||ch > '9';ch = getchar()) flag |= ch == '-';
    for(x = 0;isdigit(ch);ch = getchar()) x = (x<<1) + (x<<3) + ch - '0';
    x = flag ? -x : x;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int n,m,s; 

int head[N],rn;
struct node{int u,w,v,nex;}r[N*N];
inline void add(int a,int b,int c){
	r[++rn].u=a,r[rn].v=b,r[rn].w=c;
	r[rn].nex=head[a],head[a]=rn;
}

bool vis[N];
int dis[N],pre[N];
queue<int>q;

int tn,t[N];

inline int dy(){
	
	freopen("djs.in","r",stdin); 
	freopen("djs.out","w",stdout);
	
	in(n),in(m),in(s);
	for(R int i=1;i<=m;++i){
		R int a,b,c;in(a),in(b),in(c);
		add(a,b,c);
	}
	for(int i=0;i<n;++i)dis[i]=inf;
	dis[s]=0,vis[s]=1;
	pre[s]=-1;
	q.push(s);
	while(!q.empty()){
		R int now=q.front();q.pop();
		vis[now]=0;
		for(int i=head[now];i;i=r[i].nex){
			R int to=r[i].v;
			if(dis[now]+r[i].w<dis[to]){
				dis[to]=dis[now]+r[i].w;
				pre[to]=now;
				if(!vis[to])vis[to]=1,q.push(to);
			}
			else if(dis[now]+r[i].w==dis[to] && now<pre[to]){
				pre[to]=now;
				if(!vis[to])vis[to]=1,q.push(to);
			}
		}
	}
	for(int i=0;i<n;++i,putchar('\n')){
		write(i),putchar(':'),putchar('\n');
		if(i==s || dis[i]==inf){
			no;continue;
		}
		path;
		R int k=i;
		tn=0;
		while(k!=-1){
			t[++tn]=k;
			k=pre[k];
		}
//		putchar('0'),putchar(' ');
		for(int j=tn;j;--j,putchar(' '))write(t[j]);
		putchar('\n');
		cost;
		write(dis[i]);
	}
	exit(0);
}

int QAQ = dy();

int main(){;}