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
#include <bits/stdc++.h>
using namespace std;

struct w_edge{
	long long w;
	int n;
	w_edge(int n, long long w) : w(w), n(n) {}
};

map<pair<int, int>, int> m;
vector<w_edge> v[100002];
bool visited[100002];
long long cost[100002];
long long act[100002];

int bfs(int k){
	pair<int, long long> maxi = make_pair(0, -2000000000000000000);
	stack<int> s;
	visited[k] = 1;
	for(int i = 0; i < v[k].size(); i++){
		act[v[k][i].n] = -v[k][i].w;
		s.push(v[k][i].n);
	}
	while(!s.empty()){
		int top = s.top();
		s.pop();
		visited[top] = 1;
		if(maxi.second < act[top] + cost[top] || (maxi.second == act[top] + cost[top] && maxi.first > top)){
			maxi = make_pair(top, act[top] + cost[top]);
		}
		for(int i = 0; i < v[top].size(); i++){
			if(visited[v[top][i].n]) continue;
			act[v[top][i].n] = -v[top][i].w + act[top];
			s.push(v[top][i].n);
		}
	}
	return maxi.first;
}

int main(){
	int n, q;
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) cin>>cost[i];
	for(int i = 0; i < n - 1; i++){
		int a, b; long long c;
		scanf("%d %d %lld", &a, &b, &c);
		m[make_pair(a, b)] = v[a].size();
		m[make_pair(b, a)] = v[b].size();
		v[a].push_back(w_edge(b, c));
		v[b].push_back(w_edge(a, c));
	}
	int last = 1;
	for(int i = 0; i < q; i++){
		for(int i = 0; i <= n; i++) visited[i] = 0;
		int x; scanf("%d", &x);
		if(x == 1){
			int a; long long c;
			scanf("%d %lld", &a, &c);
			cost[a] = c;
		}
		else{
			int a, b; long long c;
			scanf("%d %d %lld", &a, &b, &c);
			v[a][m[make_pair(a, b)]].w = c;
			v[b][m[make_pair(b, a)]].w = c;
		}
		last = bfs(last);
		printf("%d ", last);
	}
}