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
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
#include <utility>  
const int MAX = 100001;

using namespace std;
class City {
public:
	long long profit;
	map<int, int> neighbors;
};

void findLargestProfit(City graph[MAX], int start, int root, long long cost, long long* max_profit, 
	int* max_profit_city, bool visited[MAX]) {
	visited[start] = true;
	long long my_profit = graph[start].profit - cost;
	if (my_profit > *max_profit || *max_profit_city == root || (my_profit == *max_profit && start < *max_profit_city)) {
		*max_profit = my_profit;
		*max_profit_city = start;
	}
	for (map<int, int>::iterator iter = graph[start].neighbors.begin(); iter != graph[start].neighbors.end(); ++iter)
	{
		if (!visited[iter->first]) {
			findLargestProfit(graph, iter->first, root, cost + iter->second, max_profit, max_profit_city, visited);
		}
	}
}

int main() {
	int n, q;
	scanf("%d", &n);
	scanf("%d", &q);
	City graph[MAX];
	bool visited[MAX];

	long long profit;
	for (int i = 1; i < n + 1; ++i) {
		scanf("%lld", &profit);
		graph[i].profit = profit;		
	}

	int from, to, toll;
	for (int i = 0; i < n - 1; ++i) {
		scanf("%d", &from);
		scanf("%d", &to);
		scanf("%d", &toll);
		graph[from].neighbors[to] = toll;
		graph[to].neighbors[from] = toll;
	}
	int opt, max_profit_city = 1;
	long long max_profit;
	for (int i = 0; i < q; ++i) {
		scanf("%d", &opt);
		if (opt == 1) {
			scanf("%d", &from);
			scanf("%lld", &graph[from].profit);
		}
		else {
			scanf("%d", &from);
			scanf("%d", &to);
			scanf("%d", &toll);
			graph[from].neighbors[to] = toll;
			graph[to].neighbors[from] = toll;
		}
		for (int j = 1; j < n + 1; ++j) visited[j] = false;
		max_profit = -1;
		findLargestProfit(graph, max_profit_city, max_profit_city, 0L, &max_profit, &max_profit_city, visited);
		printf("%d ", max_profit_city);
	}
	
	return 0;
}