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

class Graph{ 
public: 
	int n;
	int m; 
	int maxEdges;
	bool isDirected;
 
	vector<vector<int>> adj;
	vector<pair<int, pair<int, int>>> weights;
 
	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; 
		}
		
		weights.push_back({weight, {u, v}});
		
		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!!";
			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 kruskals(){
		vector<set<int>> sets;
		vector<int> finalEdges;
		
		int minSpanningWeight = 0;
		int counter = 1;
		
		sort(weights.begin(), weights.end(), 
		[](pair<int, pair<int, int>> &a, pair<int, pair<int, int>> &b){ return a.first < b.first; });
		
		for(int i = 0; i < weights.size(); ++i){
			auto val = weights[i];
			
			int uidx = -1, vidx = -1;
			
			for(int i=0; (uidx == -1 || vidx == -1) && i < sets.size(); ++i){
				if(uidx == -1 && sets[i].find(val.second.first) != sets[i].end()){
					uidx = i;
				}
				
				if(vidx == -1 && sets[i].find(val.second.second) != sets[i].end()){
					vidx = i;
				}
			}
			
			if(uidx != vidx || (uidx==-1 && vidx==-1)){
				
				finalEdges.push_back(i);
				
				minSpanningWeight += val.first;
				
				if(uidx==-1 && vidx==-1){
					set<int> st({val.second.first, val.second.second});
					
					sets.push_back(st);
				}
				else if(uidx == -1){
					sets[vidx].insert(val.second.first);
				}
				else if(vidx == -1){
					sets[uidx].insert(val.second.second);
				}
				else{
					if(uidx < vidx){
						sets[uidx].insert(sets[vidx].begin(), sets[vidx].end());
						sets[vidx].clear();
					}
					else{
						sets[vidx].insert(sets[uidx].begin(), sets[uidx].end());
						sets[uidx].clear();
					}
				}
			}
		}
		
		cout<<"The edges in the Kruskal's minimum spanning tree are,\n";
		
		for(auto idx: finalEdges){
			cout<<weights[idx].second.first<<" -> "<<weights[idx].second.second
			<<" | Weight: "<<weights[idx].first<<"\n";
		}
		
		cout<<"The minimum spanning tree weight: "<<minSpanningWeight<<"\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> &keys, int i, int tot){
		int smallest = i;
		int left = 2 * smallest + 1, right = left + 1;
		
		if(left < tot && keys[nodes[left]] < keys[nodes[smallest]])
			smallest = left;
		
		if(right < tot && keys[nodes[right]] < keys[nodes[smallest]])
			smallest = right;
			
		if(smallest ^ i){
			swap(nodes, smallest, i);
			
			swap(positions, nodes[smallest], nodes[i]);
			
			heapify(nodes, positions, keys, smallest, tot);
		}
	}
	
	void prims(int src){
		map<pair<int, int>, int> weightPairs;
		
		for(auto val: weights){
			weightPairs[val.second] = val.first;
		}
		
		/*================= Keys & predecessors initialization =================*/
		vector<int> keys(n, INT_MAX), predecessors(n, -1), nodes(n), positions(n);
		
		vector<bool> visited(n, false);
		/*================= Keys & predecessors initialization =================*/
		
		keys[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(n)]
			heapify(nodes, positions, keys, i, n);
		}
		
		/*======================= Start extracting min from heap ========================*/
		
		for(int i = n-1; i > 0; --i){ // [O(n)]
	        int u = nodes[0];
	        visited[u] = true;
	        
	        // cout<<"Popped: "<<u<<"\n";
	        
	        swap(nodes, 0, i);
	        swap(positions, nodes[0], nodes[i]);
	        
	        heapify(nodes, positions, keys, 0, i); // [O(log(n))]
			
			for(auto v: adj[u]){ // [O(m)]
				
				int weightOfUandV = weightPairs[{u, v}] ? weightPairs[{u, v}] : weightPairs[{v, u}];
				
				if(!visited[v] && weightOfUandV < keys[v]){
					// cout<<"weight: "<<weightOfUandV<<" Node: "<<v<<"\n";
					predecessors[v] = u;
					keys[v] = weightOfUandV;
					
					/*=============== Re-Position [O(log(n))] ================*/
					for(int vPos = positions[v]; 
						vPos && keys[ nodes[vPos] ] < keys[ 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(n))] ================*/
				}
			}
	    }
		
		/*======================= End of extracting min from heap ========================*/
		
		cout<<"The edges in the Prim's minimum spanning tree are,\n";
		
		int minSpanningWeight = 0;
		
		for(int u = 0; u < n; ++u){
			if(u != src){
				int v = predecessors[u];
				int wei = weightPairs[{u, v}] ? weightPairs[{u, v}] : weightPairs[{v, u}];
				
				minSpanningWeight += wei;
				
				cout<<u<<" -> "<<v<<" | Weight: "<<wei<<"\n";
			}
		}
		
		cout<<"The minimum spanning tree weight: "<<minSpanningWeight<<"\n";
		cout<<"====================================================\n";
	} 
};

int main() {
	// your code goes here
	int n, u, v, w; cin>>n;
	
	Graph g(n, 0);
	
	cin>>n;
	
	for(int i=0; i < n; ++i){
		cin>>u>>v>>w;
		g.insertEdge(u,v,w);
	}
	
	g.displayGraph();
	
	g.kruskals();
	
	cin>>u;
	cout<<"Enter the source vertex for prim's algorithm: "<<u<<"\n";
	
	g.prims(u);
	
	return 0;
}