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
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

typedef long long LL;

const int MX = 100009;
LL tab[MX];
int vis[MX];

vector< pair <int, LL > > graph[MX];

int n, q, last, ban;
LL mx, cnt;

int dfs(int flag, int s)
{
	//cout << s << ' ' << cnt << ' ' << mx << ' ' << last <<  endl;
	if(s != ban && (cnt + tab[s] > mx || (cnt + tab[s] == mx && s < last)))
	{
		mx = cnt + tab[s];
		last = s;
	}
	//cout << mx << ' ' << tab[s] <<  endl ;
	for(int i = 0; i < graph[s].size(); ++i)
	{
		if(vis[graph[s][i].first] != flag)
		{
			cnt -= graph[s][i].second;
			vis[graph[s][i].first] = flag;
			dfs(flag, graph[s][i].first);
			cnt += graph[s][i].second;
		}
	}
}


int main()
{
	ios_base :: sync_with_stdio(0);
	
	int i, j, k, a, b;
	LL c;
	
	cin >> n >> q;
	for(i = 1; i <= n; ++i) vis[i] = 0;
	for(i = 1; i <= n; ++i) cin >> tab[i];
	for(i = 0; i < n - 1; ++i)
	{
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}
	
	last = 1;
	int flag = 1;
	
	while(q--)
	{
		cin >> a;
		if(a == 1)
		{
			cin >> b >> c;
			tab[b] = c;
		}
		else 
		{
			cin >> a >> b >> c;
			for(i = 0; i < graph[a].size(); ++i) if(graph[a][i].first == b)
			{
				graph[a][i].second = c;
				break;
			}
			for(i = 0; i < graph[b].size(); ++i) if(graph[b][i].first == a)
			{
				graph[b][i].second = c;
				break;
			}
		}
		mx = cnt = -1000000000000000000;
		cnt = 0;
		vis[last] = flag;
		ban = last;
		dfs(flag, last);
		
		++flag;
		cout << last << ' '; // << "------\n";
	}
	cout << '\n';
	
	
	return 0;
}