#include <bits/stdc++.h>
using namespace std;
 
class Graph{
	public:
	int n, m;
	bool isDirected;
	vector<vector<int>> adj;
	map<pair<int, int>, int> weightPairs;
 
	Graph(int nodes): adj(nodes){
		n = nodes;
		m = 0;
	}
 
	void addEdge(int u, int v, int weight){
		if(u >= n || v >=n || u < 0 || v < 0){ 
			cout<<"Either of the vertices doesn't exists in the graph.\n";
			return;
		}
		
		weightPairs[{u, v}] = weight;
		
		adj[u].push_back(v);
		
		++m;
	}
 
	void dfs(int u, vector<bool> &visited, stack<int> &st, bool &useStack){
		visited[u] = true;
		
		if(!useStack)
			cout<<u<<" ";
 
		for(auto adjNode: adj[u]){
			if(!visited[adjNode]){
				dfs(adjNode, visited, st, useStack);
 
				if(useStack){
					st.push(adjNode);
				}
			}
		}
	}
 
	void singleSourceShortestPath(int src){
		vector<bool> visited(n, false);
		stack<int> st; // Stack for storing the topological sort of nodes. 
 
		bool useStack = true;
		
		if(!useStack)
			cout<<"DFS: ";
		
		for(int i=0; i<n; ++i){
			if(!visited[i]){
				dfs(i, visited, st, useStack);
				
				if(useStack)
					st.push(i);
			}
		}
 
		visited = vector<bool>(n, false);
		vector<int> shortestPaths(n, INT_MAX), predecessors(n, -1);
		
		shortestPaths[src] = 0;
		
		while(!st.empty()){
			int u = st.top();
			
			visited[u] = true;
			
			for(auto v: adj[u]){
				
				int distUtoV = weightPairs[{u, v}] ? weightPairs[{u, v}] : weightPairs[{v, u}];
 
				if(!visited[v] && shortestPaths[u] != INT_MAX &&
					distUtoV + shortestPaths[u] < shortestPaths[v]){
 
					predecessors[v] = u;
					shortestPaths[v] = distUtoV + shortestPaths[u];
				}
			}
 
			st.pop();
		}
		
		cout<<"The shortest paths from given source "<<src<<" to\nall other nodes are,\n";
 
			for(int u = 0; u < n; ++u){
				if(u != src){
					cout<<"----------------------------------------\n";
					if(shortestPaths[u] < INT_MAX){
						cout<<"Path length: "<<shortestPaths[u]<<" | Path: ";
						printPath(predecessors, u);
						cout<<"\n";
					}
					else{
						cout<<"No path exits from given source "<<src<<" to "<<u<<"\n";
					}
				}
			}
 
	}
 
	void printGraph(){ 
 
		if(!m){ 
			cout<<"The graph is empty!!\n";
			return;
		} 
 
		cout<<"Total # edges in the graph: "<<m<<"\n";
 
		for(int i = 0; i < n; ++i){ 
			cout<<"The edges from vertex "<<i<<":";
 
			for(auto val: adj[i])  
				cout<<"->"<<val;
 
			cout<<"\n"; 
		}
		cout<<"======================================================\n";
	}
	
	void printPath(vector<int> &predecessors, int par){
		if(par == -1)
			return;
 
		printPath(predecessors, predecessors[par]);
 
		cout<<(predecessors[par] == -1 ? "":"->")<<par;
	}
};
 
int main()
{
	int n, u, v, w; 
	cin>>n;
 
	Graph g(n);
 
	cin>>n;
 
	for(int i=0; i < n; ++i){
		cin>>u>>v>>w;
		g.addEdge(u,v,w);
	}
 
	g.printGraph();
	
	cin>>n;
	g.singleSourceShortestPath(n);
 
	return 0;
}