// A551.单源最短路径2
// https://www.acgo.cn/problemset/551/info
#include <bits/stdc++.h>
using namespace std;
int dis[1001],u,v,w,s,n,m,cnt=0;
bool boo=1;
struct node{
int u,v,w;
}e[1001];
void add(int u,int v,int w){
e[cnt]=node{u,v,w};
}
bool bellman_ford(){
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[s]=0;
for(int qwer=1;qwer<n;qwer){
boo=1;
for(int i=1;i<=m;i++){
if(dis[e[i].u]!=0x3f3f3f3f && dis[e[i].v]>dis[e[i].u]+e[i].w){
boo=0;
dis[e[i].v]=dis[e[i].u]+e[i].w;
}
}
if(boo) return 0;
}
for(int i=1;i<=m;i++) if(dis[e[i].v]!=0x3f3f3f3f && dis[e[i].v]>dis[e[i].u]+e[i].w) return 1;
return 0;
}
main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
}
if(bellman_ford()){
cout<<"no solution";
}
else{
for(int i=1;i<=n;i++){
if(dis[i]==0x3f3f3f3f) cout<<-1<<" ";
else cout<<dis[i]<<" ";
}
}
return 0;
}
