站外题求助（玄关）

预期输出：150
实际输出：151
20 42 1
25
80
17
92
18
15
73
72
10
93
26
56
62
53
14
63
37
98
100
63
12 1 90
14 10 18
20 19 29
14 2 19
17 10 38
14 16 55
20 9 37
9 5 49
7 3 68
19 9 12
11 10 89
8 17 28
1 18 34
14 1 56
17 13 11
14 4 12
8 19 37
2 1 27
13 14 5
7 6 35
5 2 33
6 14 27
9 2 72
5 14 15
16 3 70
17 3 91
4 9 39
5 13 25
10 19 12
6 4 33
1 10 37
20 7 65
3 20 96
2 13 87
5 10 83
17 19 68
6 17 53
2 4 32
15 4 21
3 5 34
12 19 37
20 16 17
4 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e15;
int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<ll> c(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> c[i];
    }
    vector<ll> a(M + 1),b(M+1),l(M+1);
    vector<vector<ll>> f(N+1,vector<ll>(N+1,INF)),g(N+1,vector<ll>(N+1,0));
    for(int i=1;i<=N;++i)
    {
    	f[i][i] = c[i];
        g[i][i] = i;
	}
    for (int i = 0; i < M; ++i) {
        int a, b, l;
        cin >> a >> b >> l;
        ll cost =l + max(c[a], c[b]);
        if (cost < f[a][b]) {
            f[a][b] = cost;
            f[b][a] = cost;
            if (c[a] > c[b]) {
                g[a][b] = a;
                g[b][a] = a;
            } else {
                g[a][b] = b;
                g[b][a] = b;
            }
        }
    }
    for(int k=1;k<=N;++k)
    {
    	for(int i=1;i<=N;++i){
            for(int j=1;j<=N;++j){
                ll m1=g[i][k],m2=g[k][j];
                if(c[m1]>c[m2])swap(m1,m2);
                if(f[i][j]>f[i][k]+f[k][j]-c[m1]){
                    f[i][j]=f[i][k]+f[k][j]-c[m1];
                    g[i][j]=m2;
                }
            }
        }
	}
    for (int i = 0; i < K; ++i) {
        int s, t;
        cin >> s >> t;
        cout << f[s][t] << endl;
    }
    
    return 0;
}