Untitled

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

long long MAX=1e15;
using ll = long long;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int V, E, S;
	cin >> V >> E;
	vector<pair<ll,pair<ll, ll>>> g(E);
	for(pair<ll,pair<ll,ll>> &e: g) {
		cin >> e.first >> e.second.first >> e.second.second;
	}
	cin >> S;
	vector<ll> dis(V, MAX);
	vector<int> parent(V, -1);
	dis[S]=0;
	for(int i=0; i<V; ++i) {
		for(pair<ll,pair<ll,ll>> &e: g) {
			ll u = e.first;
			ll v = e.second.first;
			ll w = e.second.second;
			if(dis[u]!=MAX && dis[v]>dis[u]+w) {
				parent[v]=u;
				dis[v]=dis[u]+w;
			}
		}	
	}
	bool check=1;
	for(pair<ll,pair<ll,ll>> &e: g) {
		ll u = e.first;
		ll v = e.second.first;
		ll w = e.second.second;

		if(dis[u]!=MAX && dis[v]>dis[u]+w) {
			check=0;
			break;
		}
	}
	if(check==0) cout << "Impossible!";
	else 
	for(int i=0; i<V; ++i) {
		if(i == S) {
			cout << S << ": 0\n" ;
		}else if(dis[i]==MAX) {
			cout << i << ": -1\n";
		}else {
			int v=i;
			vector<int> res;

			while(v!=-1) {
				res.push_back(parent[v]);
				v=parent[v];
			}

			int len = res.size();	
			for(int j=len-2; j>=0; --j) 
				cout << res[j] << " -> ";
			cout << i <<  ": " << dis[i] << '\n';
		}
	}

}