\(i=2,3,\ldots,M\) に対し \(s+x_i\) が正しく計算できるかを高速に判定できれば良いです。

この判定は map というデータ構造を用いることで行うことができます。詳しくは実装例を参考にしてください。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	map<pair<long, long>, long> mp;
	for (int i = 0; i < n; i++) {
		long a, b, c;
		cin >> a >> b >> c;
		mp[{a, b}] = mp[{b, a}] = c;
	}
	long s;
	cin >> s;
	for (int i = 1; i < m; i++) {
		long x;
		cin >> x;
		if (mp.contains({s, x}))
			s = mp[{s, x}];
		else
			s += x;
	}
	cout << s << endl;
}

実装例(Python3)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
mp = {}
for _ in range(n):
    a, b, c = map(int, input().split())
    mp[(a, b)] = c
    mp[(b, a)] = c
x = list(map(int, input().split()))
s = x[0]
for i in range(1, m):
    if (s, x[i]) in mp:
        s = mp[(s, x[i])]
    else:
        s += x[i]
print(s)