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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

map<pair<ll, ll>, ll> M;
ll dist[100001];
ll val[100001];
vector<ll> G[100001];
ll n, q, t, v, d, a, b, w;
ll home = 1;

void read() {
	for(ll i = 1; i <= n; i++) {
		cin >> val[i];
	}
	for(ll i = 1; i < n; i++) {
		cin >> a >> b >> w;
		M[make_pair(min(a, b), max(a,b))] = w;
		G[a].push_back(b);
		G[b].push_back(a);
	}
}

void bfs(ll source) {
	fill_n(dist, n + 1, 0);
	dist[source] = 0;
	queue <ll> Q;
	Q.push(source);
	
	while(!Q.empty()) {
		ll x = Q.front(); Q.pop();
		for(ll i = 0; i < (ll)G[x].size(); i++) {
			ll y = G[x][i];
			if(dist[y] == 0) {
				dist[y] = dist[x] - M[make_pair(min(x, y), max(x, y))];
				Q.push(y);
			}
		}
	}
	
	ll maks = -1, pos = -1;
	for(ll i = 1; i <= n; i++) {
		if(i == home) continue;
		dist[i] += val[i];
		if(dist[i] > maks) {
			maks = dist[i];
			pos = i;
		}
	}
	
	home = pos;
}

void city(ll v, ll d) {
	val[v] = d;
	bfs(home);
}

void path(ll a, ll b, ll d) {
	M[make_pair(min(a, b), max(a, b))] = d;
	bfs(home);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> q;
	
	read();
	
	while(q--) {
		cin >> t;
		
		if(t == 1) {
			cin >> v >> d;
			city(v, d);
		} else {
			cin >> a >> b >> d;
			path(a, b, d);
		}
		
		cout << home << " ";
	}
	
	cout << endl;
	
	return 0;
}