Untitled

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

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.dist<b.dist;
        }
            return a.water>b.water;
    }
};

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,dp_water[start],dp[start]});
    while(!pq.empty()){
        WD cur = pq.top();
        int cur_idx = cur.next;
        int cur_dist = cur.dist;
        int cur_water = cur.water;
        pq.pop();
        if(dp[cur_idx] < cur_dist) continue;
        for(WD next_node : graph[cur_idx]){
            int next_idx = next_node.next;
            int next_dis = cur_dist + next_node.dist;
            int next_wat = cur_water + next_node.water;
            if(next_dis <= dp[next_idx]){
                dp[next_idx] = next_dis;
                if(next_dis == dp[next_idx] && dp_water[next_idx]< next_wat){
                    dp_water[next_idx] = next_wat;
                    pq.push({next_idx,dp_water[next_idx],next_dis});
                    continue;
                }
                dp_water[next_idx] = next_wat;
                pq.push({next_idx,next_wat,dp[next_idx]});
                // vis[next_idx] = true;
            }
        }
    }
    if(dp[target]!=INF){
        cout << dp[target] << " " << dp_water[target] << endl;
        return;
    }
    cout << -1 << endl;
    return;
}

int main(void){
    ios::sync_with_stdio(false);cin.tie(0);
    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);
}