#include <bits/stdc++.h>
using namespace std;

class Graph{ 
public: 
	int n;
	int m; 
	int maxEdges;
	bool isDirected;
 
	vector<vector<int>> adj;
	map<pair<int, int>, int> weightPairs;
 
	Graph(int nodes, bool isDiGraph) : adj(nodes){ 
		n = nodes;
		m = 0;
		isDirected = isDiGraph; 
		maxEdges = isDirected ? n*(n-1) : n*(n-1)/2;
	}
 
	void insertEdge(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;
		}
 
		if(m == maxEdges){ 
			cout<<"Maximum allowed edges are already in the graph. Can't insert more.\n";
			return; 
		}
		
		if(isDirected || u != v) 
			weightPairs[{u, v}] = weight;
		
		adj[u].push_back(v); ++m;
 
		if(!isDirected && u != v)
			adj[v].push_back(u);
	} 
 
	void deleteEdge(int u, int v){ 
 
		if(u >= n || v >=n || u < 0 || v < 0){
			cout<<"Either of the vertices doesn't exists in the graph.\n";
			return;
		}
 
		auto itr = find(adj[u].begin(), adj[u].end(), v);
 
		if(itr == adj[u].end()){ 
			cout<<"The edge doesn't exists in the graph.\n";
			return; 
		} 
 
		adj[u].erase(itr); --m;
 
		if(!isDirected && u != v){
			itr = find(adj[v].begin(), adj[v].end(), u);
			adj[v].erase(itr);
		}
	} 
 
	void displayGraph(){ 
 
		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 swap(vector<int> &arr, int i, int j){
		if(arr[i] != arr[j]){
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	
	void heapify(vector<int> &nodes, vector<int> &positions,
				 vector<int> &shortestPaths, int i, int &n){
		int smallest = i;
		int left = 2 * smallest + 1, right = left + 1;
		
		if(left < n && shortestPaths[nodes[left]] < shortestPaths[nodes[smallest]])
			smallest = left;
		
		if(right < n && shortestPaths[nodes[right]] < shortestPaths[nodes[smallest]])
			smallest = right;
			
		if(smallest ^ i){
			swap(nodes, smallest, i);
			
			swap(positions, nodes[smallest], nodes[i]);
			
			heapify(nodes, positions, shortestPaths, smallest, n);
		}
	}
	
	void singleSourceShortestPath(int src){
		
		/*================= Keys & predecessors initialization =================*/
		vector<int> shortestPaths(n, INT_MAX), predecessors(n, -1), nodes(n), positions(n);
		
		vector<bool> visited(n, false);
		/*================= Keys & predecessors initialization =================*/
		
		shortestPaths[src] = 0;
		
		for(int i = 0; i < n; ++i){
			nodes[i] = i;
			positions[i] = i;
		}
		
		for(int i=n/2-1; i > -1; --i){ // [O(V)]
			heapify(nodes, positions, shortestPaths, i, n);
		}
		
		/*======================= Start extracting min from heap ========================*/
		
		for(int i = n-1; i > 0; --i){ // [O(V)]
	        int u = nodes[0];
	        visited[u] = true;
	        
	        swap(nodes, 0, i);
	        swap(positions, nodes[0], nodes[i]);
	        
	        heapify(nodes, positions, shortestPaths, 0, i); // [O(log(V))]
			
			for(auto v: adj[u]){ // [O(E)]
				
				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];
					
					/*=============== Re-Position [O(log(V))] ================*/
					for(int vPos = positions[v]; 
						vPos > 0 && shortestPaths[ nodes[vPos] ] < shortestPaths[ nodes[(vPos - 1)/2] ]; 
						vPos = (vPos - 1)/2)
					{
						swap(nodes, vPos, (vPos - 1)/2);
						swap(positions, nodes[vPos], nodes[(vPos - 1)/2]);
					}
					/*=============== Re-Position [O(log(V))] ================*/
				}
			}
	    }
		
		/*======================= End of extracting min from heap ========================*/
		
		cout<<"The shortest paths from given source 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 printPath(vector<int> &predecessors, int par){
		if(par == -1)
			return;
			
		printPath(predecessors, predecessors[par]);
		
		cout<<(predecessors[par] == -1 ? "":"->")<<par;
	}
};

int main() {
	// your code goes here
	int n, u, v, w; 
	cin>>n;
	
	Graph g(n, 1);
	
	cin>>n;
	
	for(int i=0; i < n; ++i){
		cin>>u>>v>>w;
		g.insertEdge(u,v,w);
	}
	
	g.displayGraph();
	
	cin>>u;
	cout<<"Enter the source vertex for single source shortest path\n"
	"using Dijkstra's algorithm: "<<u<<"\n";
	cout<<"------------------------------------------------------\n";
	
	g.singleSourceShortestPath(u);
	
	return 0;
}