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
#include<bits/stdc++.h>
using namespace std;
 
map< pair< int, int >, int > mapka;
vector< pair< int, int > > tab[100010];
bool met[100010];
int id, t;
int n, m;
long long cost[100010], income[100010], ans, cur, x, y, v, maks, inf = 1e18;
 
void dfs(long long w, long long ile)
{
	met[w] = 1;
	for (int a = 0; a < tab[w].size(); a++)
	{
		if (!met[tab[w][a].first])dfs(tab[w][a].first, ile - cost[tab[w][a].second]);
	}
	if( w != cur )
	{
		ile += income[w];	
		if (ile > maks)maks = ile, ans = w;
		if (ile == maks && w < ans)ans = w;
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int a = 1; a <= n; a++)cin >> income[a];
	for (int a = 1; a < n; a++)
	{
		cin >> x >> y;
		mapka[make_pair(min(x, y), max(x, y))] = ++id;
		tab[x].push_back(make_pair(y, id));
		tab[y].push_back(make_pair(x, id));
		cin >> cost[id];
	}
	cur = 1;
	for (int a = 1; a <= m; a++)
	{
		cin >> t;
		if (t == 1)
		{
			cin >> x >> v;
			income[x] = v;
		}
		else
		{
			cin >> x >> y >> v;
			cost[mapka[make_pair(min(x, y), max(x, y))]] = v;
		}
		maks = -inf;
		ans = 0;
		for (int b = 1; b <= n; b++)met[b] = 0;
		dfs(cur, 0);
		cur = ans;
		cout << cur << " ";
 
	}
	return 0;
}