Untitled

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int INF = 1000000000;

struct WD
{
    int next;
    int water;
    int dist;
};

struct cmp{
    bool operator()(const WD &a, const WD &b){
        if(a.dist==b.dist){
            return a.water<b.water;
        }
        return a.dist>  b.dist;
    }
};

int waters[100001];
int dp[100001];
int dp_water[100001];
bool vis[100001];
vector<WD> graph[100001];
int town, road, start, arrive, dis, target;

void dijstra(int start, int target){
    // 거리의 최소 with 물의 max 
    fill(dp, dp+100001, INF);
    dp[start] = 0; // 
    dp_water[start] = waters[start];
    priority_queue<WD, vector<WD>, cmp> pq;
    pq.push({start,waters[start],0});
    while(!pq.empty()){
        WD cur = pq.top();
        int cur_idx = cur.next;
        int cur_dist = cur.dist;
        int cur_water = cur.water;
        pq.pop();
        for(WD next_node : graph[cur_idx]){
            int next_idx = next_node.next;
            int next_dis = cur_dist + next_node.dist;
            if(vis[next_idx]) continue;
            if(next_dis < dp[next_dis]){
                cout << cur_idx << endl; //<< " " <<  next_idx << " " << next_dis << " " << dp[next_idx] << endl;
                dp[next_idx] = next_dis;
                if(dp_water[next_idx]<dp_water[cur_idx] + next_node.water){
                    dp_water[next_idx] = dp_water[cur_idx] + next_node.water;
                    if(!vis[next_idx]){
                        vis[next_idx] = true;
                       pq.push({next_idx,dp_water[next_idx],next_dis});
                    }
                }
            }
        }
    }
    if(dp[target]!=INF){
        cout << dp[target] << " " << dp_water[target] << endl;
        return;
    }
    // if(vis[target]){
    //     cout << dp[target] << " " << dp_water[target] << endl;
    //     return;
    // }
    cout << -1 << endl;
    return;
}

int main(void){
    cin >> town;
    for(int i = 1;i<=town;i++){
        cin >> waters[i];
    }
    cin >> road;
    while(road--){
        cin >> start >>  arrive  >> dis;
        graph[start].push_back({arrive,waters[start],dis});
        graph[arrive].push_back({start,waters[arrive], dis});
    }
    cin >> start >> target;
    dijstra(start,target);
}