1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll read() { ll n; cin >> n; return n; }

#define mp make_pair

int main() {
	int n = read();
	int t = read();
	vector<ll> z(n);
	for (int i=0; i<n; ++i) z[i] = read();
	map<pair<int, int>, ll> m;
	for (int i=1; i<n; ++i) {
		int a = read() - 1;
		int b = read() - 1;
		m[mp(a,b)] = m[mp(b,a)] = read();
	}
	
	int cur = 0;
	while (t--) {
		int cmd = read();
		if (cmd == 1) {
			int a = read() - 1;
			z[a] = read();
		}
		if (cmd == 2) {
			int a = read() - 1;
			int b = read() - 1;
			m[mp(a,b)] = m[mp(b,a)] = read();
		}
		vector<ll> v(n, -1);
		v[cur] = 0;
		queue<int> q;
		q.push(cur);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (auto it = m.lower_bound(mp(x, 0)); it != m.end() && it->first.first == x; ++it) {
				int y = it->first.second;
				if (v[y] != -1) continue;
				int k = it->second;
				v[y] = v[x] + k;
				q.push(y);
			}
		}
		int res = cur == 0 ? 1 : 0;
		for (int i=0; i<n; ++i)
			if (i != cur)
				if (z[i] - v[i] > z[res] - v[res])
					res = i;
		cout << (res+1) << " ";
		cur = res;
	}
	
	return 0;
}