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
112
113
114
115
#include <iostream>
#include <climits>
#include <vector>
#include <utility>

using namespace std;

struct Node {

	long long value;
	int node_no;
	vector<pair<Node*, int> > children;

	Node(int node, int val){
		this->node_no = node;
		this->value = val;
	}

	void changeConnectionValue(int destination, int new_val){
		for(int x=0; x<this->children.size(); x++){
			if(this->children[x].first->node_no == destination){
				this->children[x].second = new_val; 
			}
		}
	}
};

Node *cities[100000];
bool* visited;


pair<Node*, long long> findBest(Node* currentNode, long long currentScore){
	long long maxScore = currentScore + currentNode->value;
	Node* maxCity = currentNode;

	if(currentScore == 0){
		maxScore = INT_MIN;
	}

	for(int i=0; i<currentNode->children.size(); i++){
		Node* thisCity = currentNode->children[i].first;

		if(!visited[thisCity->node_no]){
			long long connectionPrice = currentNode->children[i].second;

			visited[thisCity->node_no] = true;
			pair<Node*, long long> score = findBest(cities[thisCity->node_no], currentScore - connectionPrice);
			visited[thisCity->node_no] = false;

			if(score.second > maxScore || (score.second == maxScore && score.first->node_no < maxCity->node_no)){
				maxScore = score.second;
				maxCity = score.first;
			}
		}
	}
	return make_pair(maxCity, maxScore);
}



int main(){
	int city_num, day_num;
	cin >> city_num >> day_num;

	visited = new bool[city_num];

	for(int i=0; i<city_num; i++){
		int val;
		cin >> val;

		cities[i] = new Node(i, val);
	}

	for(int i=0; i<city_num-1; i++){
		int source, destination, price;
		cin >> source >> destination >> price;
		source--; destination--;

		cities[source]->children.push_back(make_pair(cities[destination], price));
		cities[destination]->children.push_back(make_pair(cities[source], price));
	}

	int prevCity = 0;

	for(int day=0; day<day_num; day++){
		int type;
		cin >> type;

		if(type == 1){
			int city, new_val;
			cin >> city >> new_val;
			city--;

			cities[city]->value = new_val;			
		} else {
			int source, destination, new_val;
			cin >> source >> destination >> new_val;
			source--; destination--;

			cities[source]->changeConnectionValue(destination, new_val);
			cities[destination]->changeConnectionValue(source, new_val);
		}

		for(int i=0; i<city_num; i++){
			visited[i] = false;
		}
		visited[prevCity] = true;

		long long bestCity = findBest(cities[prevCity], 0).first->node_no;
		cout << bestCity+1 << " ";

		prevCity = bestCity;
	}	
	cout << "\n";
}