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
#include <cstdio>
#include <vector>
#include <bitset>
#include <unordered_map>
#include <queue>

using namespace std;

#define MX 100009
#define INF 1000000000000000009LL

static int n, q;
static vector<pair<int, long long>> edges[MX];
static unordered_map<int, int> indices[MX];
static bitset<MX> vis;
static long long profit[MX];
static pair<int, long long> que[MX];


static int solve(int start){
	int qpos = 0;
	que[qpos++] = {start, 0};
	vis = 0;
	long long best = -INF;
	int bestfor = -1;
	vis[start] = 1;
	while(qpos){
		auto cur = que[--qpos];
		for(auto e: edges[cur.first]){
			if(vis[e.first]) continue;
			vis[e.first] = 1;
			long long sumcost = cur.second + e.second;
			long long sumprofit = profit[e.first] - sumcost;
			if (sumprofit > best || (sumprofit == best && e.first < bestfor)) {
				best = sumprofit;
				bestfor = e.first;
			}
			que[qpos++] = {e.first, sumcost};
		}
	}
	return bestfor;
}

int main(){
	scanf("%d %d", &n, &q);
	for(int i=0; i<n; i++){
		scanf("%lld", &profit[i]);
	}
	for(int i=1; i<n; i++){
		int a, b;
		long long c;
		scanf("%d %d %lld", &a, &b, &c);
		a--; b--;
		indices[a][b] = edges[a].size();
		edges[a].push_back({b, c});
		indices[b][a] = edges[b].size();
		edges[b].push_back({a, c});
	}
	int cur = 0;
	while(q--){
		int type;
		scanf("%d", &type);
		if(type == 1){
			int v;
			long long d;
			scanf("%d %lld", &v, &d);
			v--;
			profit[v] = d;
		}
		else{
			int a, b;
			long long d;
			scanf("%d %d %lld", &a, &b, &d);
			a--; b--;
			edges[a][indices[a][b]].second = d;
			edges[b][indices[b][a]].second = d;
		}
		cur = solve(cur);
		printf("%d ", cur + 1);
	}
	printf("\n");
}