#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <unordered_map>
#include <climits>
#include <sstream>
#include <set>
#define LL long long

using namespace std;

#define MAX_N 100010

#define DBG(X) 

struct pair_hash {
	template <class T1, class T2>
	std::size_t operator () (const std::pair<T1, T2> &p) const {
		auto h1 = std::hash<T1>{}(p.first);
		auto h2 = std::hash<T2>{}(p.second);

		// Mainly for demonstration purposes, i.e. works but is overly simple
		// In the real world, use sth. like boost.hash_combine
		return h1 ^ h2;
	}
};

struct Tree {
	int parent;
	int level;
	// in which subtree we have best results?
	int best_first_child;
	// which of subtree's cities gives the best profit - cost ?
	int best_city_idx;
	// what is the best profit - cost ?
	LL best_total_profit; 

	string asString() {
		char buf[100];
		sprintf(buf, "(pf:%lld, bi:%d, bc:%d, parent:%d)", best_total_profit, best_city_idx, best_first_child, parent);
		return string(buf);
	}
};

struct City {
	LL profit;
	vector<int> roads;
	Tree tree;
};

enum QueryType {
	CHANGE_CITY_PROFIT = 1,
	CHANGE_ROAD_COST = 2
};


struct Query {
	QueryType type;
	int city_index;
	LL profit;

	int start_city, end_city;
	LL cost;
	Query(int city_index, int profit)
		: city_index(city_index)
		, profit(profit)
		, type(CHANGE_CITY_PROFIT)
	{
	};
	Query(int start_city, int end_city, LL cost)
		: start_city(start_city)
		, end_city(end_city)
		, cost(cost)
		, type(CHANGE_ROAD_COST)
	{

	};
};

City* cities[MAX_N];
unordered_map<pair<int, int>, LL, pair_hash> edges;
vector<Query> queries;


LL find_road_cost(const unordered_map<pair<int, int>, LL, pair_hash> &edges, int a, int b)
{
	if (a > b)
	{
		int c = a;
		a = b;
		b = c;
	}
	return edges.find(make_pair(a, b))->second;
}


LL already_visited[MAX_N];
pair<int, LL> bfs(int v, int loop_id)
{
	deque<pair<int, LL> > Q;
	LL best_profit = LLONG_MIN;
	int best_city = 0;
	// we can't stay in the same city on the same day
	already_visited[v] = loop_id;
	for (int i = 0; i < cities[v]->roads.size(); i++)
	{
		LL next_city = cities[v]->roads[i];
		Q.push_back(make_pair(next_city, find_road_cost(edges, v, next_city)));
		already_visited[next_city] = loop_id;
	}

	while (!Q.empty()) {
		pair<int, LL> current_city = Q.front();
		Q.pop_front();
		int v = current_city.first;
		LL cost_so_far = current_city.second;

		LL expected_profit = cities[v]->profit - cost_so_far;
		if (expected_profit > best_profit) {
			best_profit = expected_profit;
			best_city = v;
		}
		else if (expected_profit == best_profit && v < best_city) {
			best_city = v;
		}
		already_visited[v] = loop_id;

		vector<int> &connected_roads = cities[v]->roads;
		for (int i = 0; i < connected_roads.size(); i++)
		{
			LL next_city = connected_roads[i];
			if (already_visited[next_city] != loop_id)
			{
				// not visited
				Q.push_back(make_pair(next_city, cost_so_far + find_road_cost(edges, v, next_city)));
				already_visited[next_city] = loop_id;
			}
		}
	}
	return make_pair(best_city, best_profit);
}


void update_best_child(int node, int child)
{
	City* parent_city = cities[node];
	Tree& root_tree = parent_city->tree;
	LL cost_to_visit_child = find_road_cost(edges, node, child);
	City* child_city = cities[child];
	Tree& subtree = child_city->tree;
	LL tmp_best_child_profit = child_city->profit - cost_to_visit_child;
	int tmp_best_city_idx = child;
	if (subtree.best_total_profit != LLONG_MIN && subtree.best_total_profit - cost_to_visit_child > tmp_best_child_profit) {
		tmp_best_child_profit = subtree.best_total_profit - cost_to_visit_child;
		tmp_best_city_idx = subtree.best_city_idx;
	}
	if (tmp_best_child_profit > root_tree.best_total_profit)
	{
		root_tree.best_total_profit = tmp_best_child_profit;
		root_tree.best_city_idx = tmp_best_city_idx;
		root_tree.best_first_child = child;
	}
	if (tmp_best_child_profit == root_tree.best_total_profit)
	{
		root_tree.best_city_idx = min(root_tree.best_city_idx, tmp_best_city_idx);
	}
}

void create_tree(int node, int parent)
{
	City* c = cities[node];
	Tree& current_root = c->tree;
	current_root.parent = parent;

	for (int i = 0; i < c->roads.size(); i++)
	{
		if (c->roads[i] == parent) {
			continue;
		}
		int child_idx = c->roads[i];
		
		create_tree(child_idx, node);
	}
}

void compute_best_profits_per_subtree(int node, int parent)
{
	City* c = cities[node];
	Tree& current_root = c->tree;

	current_root.best_city_idx = -1;
	current_root.best_first_child = -1;
	current_root.best_total_profit = LLONG_MIN;

	for (int i = 0; i < c->roads.size(); i++)
	{
		if (c->roads[i] == parent) {
			continue;
		}
		int child_idx = c->roads[i];

		compute_best_profits_per_subtree(child_idx, node);

		update_best_child(node, child_idx);
	}
}

int find_tree_center(int number_of_cities)
{
	deque<int> Q;
	set<int>* nodes = new set<int>[number_of_cities+1];

	for (int i = 1; i <= number_of_cities; i++) {
		nodes[i] = set<int>(cities[i]->roads.begin(), cities[i]->roads.end());
		if (nodes[i].size() == 1) {
			Q.push_back(i);
		}
	}
	int last_processed = -1;
	while (!Q.empty()) {
		int node = Q.front();
		last_processed = node;
		Q.pop_front();
		DBG(printf("Processing leaf %d\n", node));
		// remove node for its neighbours' edge list
		for (set<int>::iterator it = nodes[node].begin(); it != nodes[node].end(); ++it)
		{
			int s = *it;
			nodes[s].erase(node);
			if (nodes[s].size() == 1) {
				Q.push_back(s);
			}
 		}
	}
	delete[] nodes;
	return last_processed;
}

void rebuild_node(int node)
{
	// either profit of city[child] has changed
	// or cost on the road from node->child has change

	City* c = cities[node];
	Tree& current_root = c->tree;
	current_root.best_city_idx = -1;
	current_root.best_first_child = -1;
	current_root.best_total_profit = LLONG_MIN;
	for (int i = 0; i < c->roads.size(); i++)
	{
		if (c->roads[i] == current_root.parent) {
			continue;
		}
		int child_idx = c->roads[i];
		update_best_child(node, child_idx);
	}
	DBG(printf("Rebuild node %d with result %s\n", node, current_root.asString().c_str()));
}

void rebuild_path(int node)
{
	while (cities[node]->tree.parent != -1)
	{
		rebuild_node(cities[node]->tree.parent);
		node = cities[node]->tree.parent;
	}
}

pair<int, LL> traverse_path_to_root(int start_city)
{
	int node = start_city;
	LL cost_on_path = 0;
	int best_city_idx = cities[start_city]->tree.best_city_idx;
	LL best_total_profit = cities[start_city]->tree.best_total_profit;
	while (cities[node]->tree.parent != -1)
	{
		cost_on_path += find_road_cost(edges, node, cities[node]->tree.parent);
		int previous = node;
		node = cities[node]->tree.parent;
		City* c = cities[node];
		if (c->tree.best_first_child == -1) {
			printf("Best first child should not be -1 at this point\n");
		}
		for (int i = 0; i < c->roads.size(); i++)
		{
			int child_idx = c->roads[i];
			if (child_idx == previous || child_idx == cities[node]->tree.parent) {
				continue;
			}
			LL cost_to_child = cost_on_path + find_road_cost(edges, node, child_idx);
			LL tmp_total_profit = cities[child_idx]->profit - cost_to_child;
			int tmp_best_child_idx = child_idx;
			Tree& subtree = cities[child_idx]->tree;
			if (subtree.best_city_idx != -1) {
				if (subtree.best_total_profit - cost_to_child > tmp_total_profit) {
					tmp_total_profit = subtree.best_total_profit - cost_to_child;
					tmp_best_child_idx = subtree.best_city_idx;
				}
				else {
					tmp_best_child_idx = min(tmp_best_child_idx, subtree.best_city_idx);
				}
			}
			if (tmp_total_profit > best_total_profit) {
				best_total_profit = tmp_total_profit;
				best_city_idx = tmp_best_child_idx;
			}
			else if (tmp_total_profit == best_total_profit) {
				best_city_idx = min(best_city_idx, tmp_best_child_idx);
			}
		}
		/*
		if (c->tree.best_first_child != previous) {
			LL tmp_profit = c->tree.best_total_profit - cost_on_path;
			if (tmp_profit > best_total_profit) {
				best_total_profit = tmp_profit;
				best_city_idx = c->tree.best_city_idx;
			}
			else if (tmp_profit == best_total_profit) {
				best_city_idx = min(best_city_idx, c->tree.best_city_idx);
			}
		}
		*/
		if (c->profit - cost_on_path > best_total_profit) {
			best_total_profit = c->profit - cost_on_path;
			best_city_idx = node;
		}
		else if (c->profit - cost_on_path == best_total_profit) {
			best_city_idx = min(best_city_idx, node);
		}
	}
	return make_pair(best_city_idx, best_total_profit);
}

void print_city_rec(int node)
{
	City* c = cities[node];
	Tree& current_root = c->tree;
	printf("Node: %d tree:%s\n", node, current_root.asString().c_str());
	for (int i = 0; i < c->roads.size(); i++) {
		if (c->roads[i] == current_root.parent) {
			continue;
		}
		print_city_rec(c->roads[i]);
	}
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)
	{
		City* c = new City();
		scanf("%lld", &c->profit);
		cities[i] = c;
	}
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		LL cost;
		scanf("%d%d%lld", &a, &b, &cost);
		cities[a]->roads.push_back(b);
		cities[b]->roads.push_back(a);
		if (a > b)
		{
			swap(a, b);
		}
		edges[make_pair(a, b)] = cost;
	}
	for (int i = 0; i < q; i++)
	{
		int type;
		scanf("%d", &type);
		if (type == 1)
		{
			int vi;
			LL di;
			scanf("%d%lld", &vi, &di);
			queries.push_back(Query(vi, di));
		}
		else {
			int ai, bi;
			LL di;
			scanf("%d%d%lld", &ai, &bi, &di);
			if (ai > bi) {
				swap(ai, bi);
			}
			queries.push_back(Query(ai, bi, di));
		}
	}

	int global_tree_root = find_tree_center(n);
	create_tree(global_tree_root, -1);

	compute_best_profits_per_subtree(global_tree_root, -1);
	
	DBG(print_city_rec(global_tree_root));

	int current_city = 1;
	for (int i = 0; i < queries.size(); i++)
	{
		Query query = queries[i];
		DBG(printf("\n #%d query\n", i + 1));
		if (query.type == CHANGE_CITY_PROFIT)
		{
			cities[query.city_index]->profit = query.profit;
			rebuild_path(query.city_index);
		}
		else if (query.type == CHANGE_ROAD_COST) {
			edges[make_pair(query.start_city, query.end_city)] = query.cost;
			if (cities[query.start_city]->tree.parent == query.end_city) {
				rebuild_path(query.start_city);
			}
			else if (cities[query.end_city]->tree.parent == query.start_city) {
				rebuild_path(query.end_city);
			}
			else {
				printf("Internal error of edge\n");
			}
		}
		DBG(print_city_rec(global_tree_root));

		// Solution1:
		//pair<int, LL> result = bfs(current_city, i+1);
		
		// Solution2: 
		pair<int, LL> result = traverse_path_to_root(current_city);
		DBG(printf("(%d, %lld)\n", result.first, result.second));
		printf("%d ", result.first);
		// 
		current_city = result.first;
	}
}