#include using namespace std; #include #include #include #include #include template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #define rep(i,n) for (int i = 0; i < (n); ++i) typedef long long ll; using P=pair; const ll INF=1e18; const int mod=998244353; struct edge{ int to; ll w; edge(int to,ll w):to(to),w(w){} }; void solve(){ int n,s,t,k,m; cin>>n>>s>>t>>k; s--;t--; vectorx(n); rep(i,n){cin>>x[i];} cin>>m; vector>G(n); rep(i,m){ int a,b,y; cin>>a>>b>>y;a--;b--; G[a].emplace_back(b,x[b]+y); } vector>dist(k+1,vector(n,INF)); vector>prev(k+1,vector(n,-1)); vector>prec(k+1,vector(n,-1)); priority_queue>,vector>>,greater>>>q; q.push(make_pair(x[s],make_pair(0,s))); dist[0][s]=x[s]; while(!q.empty()){ int c=q.top().second.first; int v=q.top().second.second; ll cost=q.top().first; q.pop(); if(cost!=dist[c][v]){continue;} for(auto u:G[v]){ int nc=min(k-1,c+1); if(chmin(dist[nc][u.to],cost+u.w)){ prev[nc][u.to]=v; prec[nc][u.to]=c; q.push(make_pair(dist[nc][u.to],make_pair(nc,u.to))); } } } if(dist[k-1][t]==INF){ cout<<"Impossible"<ans; int p=t,pc=k-1; while(pc!=-1){ ans.push_back(p); int np=pc; pc=prec[np][p]; p=prev[np][p]; } reverse(ans.begin(),ans.end()); cout<