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
#include <stdio.h>
#include <map>
#include <list>
typedef long long i64;
using namespace std;

const int MAX = 100028;
//const long long mINF = -9223372036854775807LL;
const long long mINF = -999999;
int q, n;
i64 z[MAX];
int p[MAX];
list<int> g[MAX];
map<i64,i64> m;

i64 f(i64 a, i64 b) { return min(a,b)*MAX + max(a,b); }
int kolejka = 0;

typedef pair<int, i64> best;

void improve(best& a, const best& b)
{
	//printf("(%d,%lld)-(%d,%lld) ", a.first, a.second, b.first, b.second);
	if (b.first != -1) {
		if (a.first == -1) a=b;
		if (a.second<b.second) a=b;
	}
	//printf("->(%d,%lld)\n", a.first, a.second);
}

best dfs(int r) {
	if (p[r]==kolejka) return best(-1,mINF);
	p[r]=kolejka;
	best so_far(-1,mINF);
	for (auto b: g[r]) {
		if (p[b]==kolejka) continue;
		//printf("r->b: %d %d\n", r, b);
		i64 cost = m[f(r,b)];
		best cand = dfs(b);
		cand.second -= cost;
		improve(so_far, cand);
		improve(so_far, best(b,z[b]-cost));
	}
	return so_far;
}

int main()
{
	scanf("%d %d", &n, &q);
	for (int i=1; i<=n; i++)
		scanf("%lld", &z[i]);
	for (int i=1; i<n; i++) {
		int a,b;
		i64 c;
		scanf("%d %d %lld", &a,&b,&c);
		g[a].push_back(b);
		g[b].push_back(a);
		m[f(a,b)]=c;
	}
	best at = best(1,0);
	for (kolejka=1; kolejka<=q; kolejka++) {
		int t, v, a, b; i64 d;
		scanf("%d", &t);
		if (t==1) {
			scanf("%d %lld", &v, &d);
			z[v]=d;
		} else {
			scanf("%d %d %lld", &a, &b, &d);
			m[f(a,b)]=d;
		}
		at = dfs(at.first);
		printf("%d ", at.first);
	}
	printf("\n");
	return 0;
}