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
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL INF = 2e18 + 10LL;
const int mxn = 1e5 + 10;

int n, q;

vector <int> V[mxn];
map < pair <int, int>, LL > E;
LL czas[mxn];


void wczytaj()
{
	scanf("%d%d", &n, &q);
	
	for(int i = 1; i <= n; i++)
		scanf("%lld", &czas[i]);
		
	for(int i = 2; i <= n; i++)
	{
		int a, b;
		LL c;
		scanf("%d%d%lld", &a, &b, &c);
		E[{a, b}] = c;
		E[{b, a}] = c;
		V[a].push_back(b);
		V[b].push_back(a);
	}
}

int pocz;
LL maks;
int id;

void dfs(int v, int par, LL odl)
{
	if(czas[v] - odl >= maks && v != pocz)
	{
		if(czas[v] - odl == maks)
			id = min(v, id);
		else
			id = v;
			
		maks = max(maks, czas[v] - odl);
	}
	
	for(auto u : V[v])
	{
		if(u == par)
			continue;
		
		dfs(u, v, odl + E[{u, v}]);
	}
}

int main()
{
	wczytaj();
	int v = 1;
	for(int i = 1; i <= q; i++)
	{
		int typ;
		scanf("%d", &typ);
		if(typ == 1)
		{
			int a;
			LL b;
			scanf("%d%lld", &a, &b);
			czas[a] = b;
			
			id = n + 1;
			maks = -INF;
			pocz = v;
			dfs(v, v, 0LL);
			
			v = id;
		}
		else
		{
			int a, b;
			LL c;
			scanf("%d%d%lld", &a, &b, &c);
			E[{a, b}] = c;
			E[{b, a}] = c;
			
			id = n + 1;
			maks = -INF;
			pocz = v;
			dfs(v, v, 0LL);
			
			v = id;
		}
		printf("%d ", v);
	}
	printf("\n");
	return 0;
}