今回の問題は所要時間が最短となるようなものの中で満足度が最大となるようなものを求める問題なので、最短経路問題を解くアルゴリズム、特に Dijkstra 法を工夫してこの問題を解くことを考えます。以下、所要時間は距離と言い換えます。

まず、それぞれの都市の景観を \(1\) 度しかカウントしないという条件下では基本的にそれぞれの都市を通ったかどうかの情報を持っておく必要があり解くのが難しいです。
しかし、今それぞれの道路は正の距離を持っているため、都市 \(1\) から都市 \(N\) までの最短経路としてあり得るものの中に同じ都市を \(2\) 度以上訪れるようなものはなく、各都市の景観を訪れる度に満足度に加えるとしても問題の答えは変わらない事が分かります。以下、この問題を解くことを考えます。

都市 \(1\) を開始都市とした Dijkstra 法では各都市について都市 \(1\) から都市 \(i\) への最短距離 \(D_i\) を持っておき、距離が一番短い都市から順に確定していく事で問題を解きます。今回は各都市について、都市 \(1\) から都市 \(i\) への最短距離 \(D_i\) と、都市 \(1\) から都市 \(i\) への距離 \(D_i\) の経路のうち満足度が最大のものの満足度 \(X_i\) を持っておけばよいです。 確定させる順番は通常の Dijkstra 法と同じく、都市 \(1\) からの所要時間が短い順で良いです。 これは都市 \(1\) から都市 \(i\) への距離が都市 \(1\) から都市 \(j\) (\(i\neq j\)) への距離以上であるとき、都市 \(1\) から都市 \(i\) を経由して都市 \(j\) に向かうような経路が最短となることは無く、候補として考慮する必要は無いからです。

よって、優先度付きキュー等を用いた Dijkstra 法を実装することでこの問題を \(O(M\log M)\) (実際には \(O(N+M\log M)\) であるが、\(M\geq N-1\) より \(O(N)\) の部分は書かなくて良い) で解くことができ、十分高速です。

C++による実装例:

#include <bits/stdc++.h>

using namespace std;

#define N 100010
#define INF (ll)4e+18
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	int n, m;
	ll a[N];
	vector<pair<int, ll> >e[N];

	ll d[N];
	ll mx[N];
	bool fix[N];
	priority_queue < pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > >pq;

	int u, v, cur, nxt;
	ll x, dd;

	cin >> n >> m;
	rep(i, n)cin >> a[i];
	rep(i, m) {
		cin >> u >> v >> x;
		e[u - 1].push_back({ v - 1,x });
		e[v - 1].push_back({ u - 1,x });
	}

	d[0] = 0;
	for (int i = 1; i < n; i++)d[i] = INF;
	mx[0] = a[0];
	for (int i = 1; i < n; i++)mx[i] = (ll)0;
	for (int i = 0; i < n; i++)fix[i] = false;
	pq.push({ (ll)0,0 });

	while (true) {
		while (fix[cur = pq.top().second])pq.pop();
		if (cur == n - 1)break;
		fix[cur] = true;
		pq.pop();
		for (int i = 0; i < e[cur].size(); i++) {
			nxt = e[cur][i].first;
			dd = e[cur][i].second;
			if ((d[cur] + dd) < d[nxt]) {
				pq.push({ d[nxt] = d[cur] + dd,nxt });
				mx[nxt] = mx[cur] + a[nxt];
			}
			else if ((d[cur] + dd) == d[nxt]) {
				mx[nxt] = max(mx[nxt], mx[cur] + a[nxt]);
			}
		}
	}
	cout << mx[n - 1] << endl;

	return 0;
}