przemtynicy

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
int n,tab[5005],m,a,b,c,t[5005],k[5005],wynik=1000000000;
vector <pair<int,int> > v1[5005];
vector <pair<int,int> > v2[5005];
priority_queue <pair<int,int > >q;
pair <int,int> g[5005];
int main()
{
   scanf("%d",&n);
    for(int i=1;n>=i;i++)
    {
        scanf("%d",&tab[i]);
    }
    scanf("%d",&m);
    for(int i=1;m>=i;i++)
    {
         scanf("%d %d %d" ,&a,&b,&c);
        v1[a].push_back({c,b});
        v2[b].push_back({c,a});
    }
    q.push({0,1});
    t[1]=0;
    while(q.empty()==0)
    {
        int s=q.top().second;
        int r=q.top().first;
        q.pop();
        if(t[s])
            continue;
        t[s]=-1*r;
        g[s].first=1;
        for(int i=0;v1[s].size()>i;i++)
        {
            if(t[v1[s][i].second]==0 and v1[s][i].second!=1)
            {q.push({(t[s]+v1[s][i].first)*(-1),v1[s][i].second});}
        }
    }
     q.push({0,1});
    while(q.empty()==0)
    {
        int s=q.top().second;
        int r=q.top().first;
        q.pop();
        if(k[s])
            continue;
             k[s]=-1*r;
             g[s].second=1;
        for(int i=0;v2[s].size()>i;i++)
        {
            if(k[v2[s][i].second]==0 and v2[s][i].second!=1 )
            {q.push({(k[s]+v2[s][i].first)*(-1),v2[s][i].second});}
        }
    }
for(int i=1;n>=i;i++)
{
if(g[i].first==1 and g[i].second==1)
    wynik=min(wynik,t[i]+k[i]+tab[i]/2);
}
printf("%d",wynik);
}