#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; 
		}
 
		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 singleSourceShortestPath(int src){
 
		/*================= Keys & predecessors initialization =================*/
		vector<int> shortestPaths(n, INT_MAX), predecessors(n, -1);
		/*================= Keys & predecessors initialization =================*/
		
		shortestPaths[src] = 0;
		
		int u, v;
		
		for(int i=1; i<n; ++i){
			
			for(auto &edge: weightPairs){
				
				u = edge.first.first, v = edge.first.second;
				
				int distUtoV = edge.second;
					
				if(shortestPaths[u] != INT_MAX && shortestPaths[u] + distUtoV < shortestPaths[v]){
					predecessors[v] = u;
					shortestPaths[v] = shortestPaths[u] + distUtoV;
				}
			}
			
		}
		
		bool flag = true;
			
		for(auto &edge: weightPairs){
				
			u = edge.first.first, v = edge.first.second;
				
			int distUtoV = edge.second;
			
			if(shortestPaths[u] != INT_MAX && shortestPaths[u] + distUtoV < shortestPaths[v]){
				cout<<"Graph contains negative cycles.\n"
				"No shortest path exits from given source to other nodes.\n";
				flag = false;
				break;
			}
		}
		
		if(flag){
			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 Bellman-Ford algorithm: "<<u<<"\n";
	cout<<"------------------------------------------------------\n";
 
	g.singleSourceShortestPath(u);
 
	return 0;
}