```cpp #include <iostream> #define INF 9999 using namespace std; struct node { int node,next; int weight; }edge[10000]; int first_arc[300],cnt; void addEdge(int x,int y,int w) { edge[cnt].node=y; edge[cnt].next=first_arc[x]; first_arc[x]=cnt; edge[cnt].weight=w; ++cnt; } int main() { int n,m,u,v,w,start; cin>>n>>m>>start; for(int i=0;i<n;++i) first_arc[i]=-1; for(int i=0;i<m;++i) { cin>>u>>v>>w; addEdge(u,v,w); } int dist[100],s[100],path[100]; for(int i=0;i<n;++i) { dist[i]=INF; s[i]=0; path[i]=-1; } int p=first_arc[start]; while(p!=-1) { dist[edge[p].node]=edge[p].weight; path[edge[p].node]=start; p=edge[p].next; } s[start]=1; path[start]=0; int min_dist,k; for(int i=0;i<n;++i) { min_dist=INF; for(int j=0;j<n;++j) if(s[j]==0&&dist[j]<min_dist) { k=j; min_dist=dist[j]; } s[k]=1; p=first_arc[k]; while(p!=-1) { int t=edge[p].node; if(s[t]==0&&dist[k]+edge[p].weight<dist[t]) { dist[t]=dist[k]+edge[p].weight; path[t]=k; } p=edge[p].next; } } int output[100],out_cnt,t; for(int i=0;i<n;++i) if(s[i]==1&&i!=start) { cout<<start<<" to "<<i<<" with length "<<dist[i]<<" :"; out_cnt=0; output[out_cnt]=i; t=path[i]; if(t==-1) cout<<"no path"<<endl; else { while(t!=start) { ++out_cnt; output[out_cnt]=t; t=path[t]; } ++out_cnt; output[out_cnt]=start; cout<<output[out_cnt]; for(int j=out_cnt-1;j>=0;--j) cout<<','<<output[j]; cout<<endl; } } } ```