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
#include <cstdio>
#include <vector>
#include <map>
#include <string.h>
#include <climits>

using namespace std;

const int MAX_N=100007;

int n, q, a, b, act_city;
long long c, act;
long long z[MAX_N];
vector <int> pol[MAX_N];
pair <long long, int> out;
map <pair <int, int>, long long> cost;
bool visited[MAX_N];


void dfs(int from, int now) {
	visited[now]=1;
	if(now!=from) {
		if(act+z[now]>out.first) {
			out.first=act+z[now];
			out.second=now;
		}
		else if(act+z[now]==out.first && now<out.second) {
			out=make_pair(act+z[now], now);
		}
	}
	for(int i=0; i<pol[now].size(); i++) {
		if(!visited[pol[now][i]]) {
			act-=cost[make_pair(now, pol[now][i])];
			dfs(from, pol[now][i]);
			act+=cost[make_pair(now, pol[now][i])];
		}
	}
}

int main() {
	scanf("%d%d", &n, &q);
	for(int i=1; i<=n; i++) {
		scanf("%lld", &z[i]);
	}
	for(int i=0; i<n-1; i++) {
		scanf("%d%d%lld", &a, &b, &c);
		pol[a].push_back(b);
		pol[b].push_back(a);
		cost[make_pair(a,b)]=c;
		cost[make_pair(b,a)]=c;
	}
	act_city=1;
	for(int i=0; i<q; i++) {
		memset(visited, 0, sizeof(visited));
		out=make_pair(LONG_LONG_MIN, 0);
		act=0;
		scanf("%d", &a);
		if(a==1) {
			scanf("%d%lld", &b, &c);
			z[b]=c;
		}
		else {
			scanf("%d%d%lld", &a, &b, &c);
			cost[make_pair(a,b)]=c;
			cost[make_pair(b,a)]=c;
		}
		dfs(act_city, act_city);
		act_city=out.second;
		printf("%d ", act_city);
	}
}