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
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;

template <typename T> T load() {
	T r;
	cin >> r;
	return r;
}
template <typename T> vector<T> loadMany(int n) {
	vector<T> rs(n);
	generate(rs.begin(), rs.end(), &load<T>);
	return rs;
}

struct Graph {
	Graph(int n):edges(n){}
	void addEdge2(int a, int b, long long w){
		addEdge1(a,b);
		addEdge1(b,a);
		edgeWeight(a,b) = w;
	}
	int size() const {return edges.size();}
	long long& edgeWeight(int a, int b){
		return weights[edgeUID(a, b)];
	}
	template <typename PreV, typename PostV, typename PreE, typename PostE, typename FailE> void DFS(int source, PreV prev, PostV postv, PreE pree, PostE poste, FailE faile) const {
		auto visited = vector<bool>(size(), false);
		implDFS(source, visited, prev, postv, pree, poste, faile);
	}
private:
	template <typename PreV, typename PostV, typename PreE, typename PostE, typename FailE> void implDFS(int vertex, vector<bool>& visited, PreV prev, PostV postv, PreE pree, PostE poste, FailE faile) const {
		prev(vertex);
		for (auto kid : edges[vertex])
			if (not visited[kid])
				visited[kid] = true, pree(vertex, kid), implDFS(kid, visited, prev, postv, pree, poste, faile), poste(vertex, kid);
			else
				faile(vertex, kid);
		postv(vertex);
	}
	void addEdge1(int a, int b){edges[a].push_back(b);}
	long long edgeUID(int a, int b) {
		if (a > b) swap(a, b);
		return static_cast<long long>(a) * size() + b;
	}
	vector<vector<int>> edges;
	unordered_map<long long, long long> weights;
};

Graph loadEdges(int n, int m) {
	auto graph = Graph(n);
	for (int i=0; i<m; ++i) {
		auto a = load<int>() - 1;
		auto b = load<int>() - 1;
		auto w = load<long long>();
		graph.addEdge2(a, b, w);
	}
	return graph;
}
template <typename F1, typename F2> void doQueries(int q, F1 f1, F2 f2) {
	for (int i=0; i<q; ++i) {
		auto type = load<int>();
		if (type == 1) {
			auto v = load<int>() - 1;
			auto dprim = load<long long>();
			f1(v, dprim);
		} else {
			auto a = load<int>() - 1;
			auto b = load<int>() - 1;
			auto wprim = load<long long>();
			f2(a, b, wprim);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto n = load<int>();
	auto q = load<int>();
	auto profits = loadMany<long long>(n);
	auto graph = loadEdges(n, n-1);
	auto currentVertex = 0;
	auto brut = [&]() -> long long {
		auto currCost = 0ll;
		auto maxVertex = -1;
		auto maxResult = numeric_limits<long long>::min();
		graph.DFS(currentVertex, [&](int pre){
			auto thisResult = max(maxResult, profits[pre] - currCost);
			if (make_pair(maxResult, -maxVertex) < make_pair(thisResult, -pre) and pre != currentVertex) {
				maxResult = thisResult;
				maxVertex = pre;
			}
		}, [&](int){}, [&](int prea, int preb){
			currCost += graph.edgeWeight(prea, preb);
		}, [&](int posta, int postb){
			currCost -= graph.edgeWeight(posta, postb);
		}, [&](int,int){});
		currentVertex = maxVertex;
		return maxVertex;
	};
	doQueries(q, [&](int vertex, int newProfit){
		profits[vertex] = newProfit;
		auto result = brut();
		cout << (result+1) << ' ';
	}, [&](int vert1, int vert2, int newCost){
		graph.edgeWeight(vert1, vert2) = newCost;
		auto result = brut();
		cout << (result+1) << ' ';
	});
	cout << '\n';
}