Untitled

#include <bits/stdc++.h>
#define pii pair<ll, ll> // 생성자 ok
typedef long long ll;
using namespace std;

const ll MAX = 100001;
ll C[MAX], D[MAX], TD[MAX];
vector<pii> G[MAX], TG[MAX];
int indegree[100001];

void Dijstra(int cur){
    fill(D, D + MAX, 1E18);
    D[cur] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> PQ;
    PQ.emplace(0,cur);
    while(!PQ.empty()){
        auto [cd, cur] = PQ.top(); PQ.pop();
        if(cd > D[cur]) continue;
        for(auto & [next, nd] : G[cur]){
            if(D[next]<=D[cur]+nd) continue;
            PQ.emplace(D[next] = D[cur] + nd, next);
        }
    }
}


void topologcialSort(ll &n, ll & target){
    queue<int> que;
    ll ret = 0;
    for(int i = 1 ;i<=n;i++){
        if(indegree[i]==0){
            que.push(i);
            TD[i] = C[i];
        }
    }

    while(!que.empty() && indegree[target]){
        int x = que.front();
        que.pop();
        for(int j = 0; j< TG[x].size();j++){
            int next = TG[x][j].first;
            TD[next] = max(TD[next], TD[x] + C[next]);            
            if(--indegree[next]==0){
                que.push(next);
            }
        }
    }
    return;
}

int main(void){
    ios::sync_with_stdio(false);cin.tie(0);
    ll N, M;
    cin >> N;
    for(int i = 1;i<=N;i++) cin >> C[i];
    cin >> M;
    for(int j = 1;j<=M;j++){
        ll u, v, d;
        cin >> u >> v >> d;
        G[u].emplace_back(v,d);
        G[v].emplace_back(u,d);
    }
    ll s,t;
    cin >> s >> t;
    Dijstra(s);
    // s를 기준으로 나머지 vertex의 최단거리를 D에 기록했음
    
    for(int i = 1; i <= N; i++){
        sort(G[i].begin(), G[i].end()); // 가장 작은 것부터 시작
        for(auto &[next, nd] : G[i]){
            if(D[next] + nd != D[i]) continue; // 현재부터 다음 dist를 더했을 때 같아야 된다.
	        TG[next].emplace_back(i, C[i]); // i -> next -> next_next
            indegree[next]++;               
	        break;
        }
    }
    
    for(int i = 1;i<=N;i++) {
        cout << D[i] << " ";
    }
    cout <<  endl;
    topologcialSort(N,t);
    for(int i = 1;i<=N;i++) {
        cout << TD[i] << " ";
        // TD[i] = C[i]
    }
    cout << endl;
    if(D[t] != 1E18){
        cout << D[t] << " " << TD[t]  << endl;
    }
    else{
        cout << -1 << endl;
    }
}