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){
        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,0});
    while(!pq.empty()){
        WD cur = pq.top();
        int cur_idx = cur.next;
        int cur_dist = cur.dist;
        pq.pop();
        if(cur_idx == target){
            cout << cur_dist << " " << dp_water[target] << endl;
            return;
        }
        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_water[next_idx] = max(dp_water[next_idx],dp_water[cur_idx] + waters[next_idx]);
                dp[next_idx] = next_dis;
                if(!vis[next_idx]){
                    vis[next_idx] = true;
                    pq.push({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,dis});
        graph[arrive].push_back({start,dis});
    }
    cin >> start >> target;
    dijstra(start,target);
}