#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

#define N 110

#define M 10100

#define qm 110

#define INF 0x3f3f3f3f

int path[N][N] = {0};

int n,m,st;

int q[qm + 1];

int dis[N];

bool v[N];

int map[N][N];

void spfa(int s){

 for (int i = 0; i < n; i++){

 if (map[s][i] != INF){

 path[i][0] = 2;

 path[i][1] = s;

 path[i][2] = i;

 }

 else path[i][0] = 0;

 }

 path[s][0]--;

 memset(v,0,sizeof(v));

 memset(dis,0x3f,sizeof(dis));

 dis[s] = 0;

 int h = 0,t = 0;

 q[++t] = s;

 while (h != t){

 int x = q[h = (h % qm) + 1];

 v[x] = 0;

 for (int i = 0; i < n; i++){

 if (map[x][i] != INF){

 if (dis[i] > dis[x] + map[x][i]){

 dis[i] = dis[x] + map[x][i];

 for (int j = 1; j <= path[x][0]; j++){

 path[i][j] = path[x][j];

 }

 path[i][0] = path[x][0];

 path[i][++path[i][0]] = i;

 if (!v[i]){

 t = (t % qm) + 1;

 q[t] = i;

 v[i] = 1;

 }

 }

 }

 }

 }

 return;

}

int main(){

 freopen("djs.in","r",stdin);

 freopen("djs.out","w",stdout);

 memset(map,0x3f,sizeof(map));

 scanf("%d%d%d",&n,&m,&st);

 int x,y,z;

 for (int i = 1; i <= m; i++){

 scanf("%d%d%d",&x,&y,&z);

 map[x][y] = z;

 }

 for (int i = 0; i < n; i ++) map[i][i] = 0;

 spfa(st);

 for (int i = 0; i < n; i++){

 printf("%d:\n",i);

 if (dis[i] != INF && i != st){

 printf("path:");

 for (int j = 1; j <= path[i][0]; j++){

 printf("%d ",path[i][j]);

 }

 puts("");

 printf("cost:%d\n",dis[i]);

 }else{

 puts("no");

 }

 }

 return 0;

}