#include using namespace std; const long long INF = (1LL << 60); #line 2 "segment-tree/segment-tree.hpp" template struct SegmentTree { int N; int size; vector seg; const F f; const T I; SegmentTree(F _f, const T &I_) : N(0), size(0), f(_f), I(I_) {} SegmentTree(int _N, F _f, const T &I_) : f(_f), I(I_) { init(_N); } SegmentTree(const vector &v, F _f, T I_) : f(_f), I(I_) { init(v.size()); for (int i = 0; i < (int)v.size(); i++) { seg[i + size] = v[i]; } build(); } void init(int _N) { N = _N; size = 1; while (size < N) size <<= 1; seg.assign(2 * size, I); } void set(int k, T x) { seg[k + size] = x; } void build() { for (int k = size - 1; k > 0; k--) { seg[k] = f(seg[2 * k], seg[2 * k + 1]); } } void update(int k, T x) { k += size; seg[k] = x; while (k >>= 1) { seg[k] = f(seg[2 * k], seg[2 * k + 1]); } } void add(int k, T x) { k += size; seg[k] += x; while (k >>= 1) { seg[k] = f(seg[2 * k], seg[2 * k + 1]); } } // query to [a, b) T query(int a, int b) { T L = I, R = I; for (a += size, b += size; a < b; a >>= 1, b >>= 1) { if (a & 1) L = f(L, seg[a++]); if (b & 1) R = f(seg[--b], R); } return f(L, R); } T &operator[](const int &k) { return seg[k + size]; } // check(a[l] * ... * a[r-1]) が true となる最大の r // (右端まですべて true なら N を返す) template int max_right(int l, C check) { assert(0 <= l && l <= N); assert(check(I) == true); if (l == N) return N; l += size; T sm = I; do { while (l % 2 == 0) l >>= 1; if (!check(f(sm, seg[l]))) { while (l < size) { l = (2 * l); if (check(f(sm, seg[l]))) { sm = f(sm, seg[l]); l++; } } return l - size; } sm = f(sm, seg[l]); l++; } while ((l & -l) != l); return N; } // check(a[l] * ... * a[r-1]) が true となる最小の l // (左端まで true なら 0 を返す) template int min_left(int r, C check) { assert(0 <= r && r <= N); assert(check(I) == true); if (r == 0) return 0; r += size; T sm = I; do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!check(f(seg[r], sm))) { while (r < size) { r = (2 * r + 1); if (check(f(seg[r], sm))) { sm = f(seg[r], sm); r--; } } return r + 1 - size; } sm = f(seg[r], sm); } while ((r & -r) != r); return 0; } }; int main() { int N, M, K; cin >> N >> M >> K; vector S(K+1, 0); for(int i = 0; i < K+1; i++) { cin >> S[i]; S[i]--; } vector A(M, 0), B(M, 0); vector C(M, 0LL); vector dist(N, vector(N, INF)); for(int i = 0; i < M; i++) { cin >> A[i] >> B[i] >> C[i]; A[i]--, B[i]--; dist[A[i]][B[i]] = C[i]; dist[B[i]][A[i]] = C[i]; } for(int k = 0; k < N; k++) { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]); } } } int Q; cin >> Q; vector T(Q, 0), X(Q, 0), Y(Q, 0); for(int i = 0; i < Q; i++) cin >> T[i] >> X[i] >> Y[i]; auto op = [](long long a, long long b) { return (a+b); }; SegmentTree segtree(K, op, 0LL); for(int i = 0; i < K; i++) { segtree.update(i, dist[S[i]][S[i+1]]); } for(int i = 0; i < Q; i++) { if(T[i] == 1) { Y[i]--; S[X[i]] = Y[i]; if(0 <= X[i]-1) segtree.update(X[i]-1, dist[S[X[i]-1]][S[X[i]]]); if(X[i]+1 < K+1) segtree.update(X[i], dist[S[X[i]]][S[X[i]+1]]); } if(T[i] == 2) { cout << segtree.query(X[i], Y[i]) << endl; } } return 0; }