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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#define LL long long
#define MAX 100001
#define INF 1000000000000000000
#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;

struct TAC {  // town and cost
	int town;
	LL cost;
};

//siec miast i drog
vector< pair<int,LL> > graf[MAX];
LL Z[MAX];
LL ZMAX = -1;
int n, q; // ilosc miast, ilosc dni

//kolejka miast do przejscia
TAC Q[MAX];
int head = 0, tail = 0;
TAC queue_front() {
	return Q[head++];	
}
int queue_push(TAC x ) {
	
	Q[tail++] = x;
}
bool queue_empty() {
	return head == tail;
}

int bfs(int v) {
    LL max_cost;
	vector<int> visited(n+1,0); // 1- miasto odwiedzone, 0 - jeszcze nie
	int best_next_town_so_far = 0; // najlepsze nastepne miasto
	LL best_so_far= -INF;  // najlepszy wynik do tej pory
	LL cost_so_far;  // suma oplat na dotarcie do tego miasta 
	TAC next_town, cur_town;
	cur_town.town = v;
	cur_town.cost = 0;
	queue_push(cur_town);
	visited[v] = 1;
	
	while (!queue_empty()) {
		TAC cur = queue_front();  // biezace miasto
		int u = cur.town;
		// moze to najlepszy wynik sprawdz i zapamietaj
		LL zysk;
		if(u!=v) {
		zysk= Z[u]-cur.cost;} else zysk =-INF;
		if(zysk>best_so_far) {
			best_so_far = zysk;
			best_next_town_so_far = u;
		} else
		if(zysk==best_so_far){
			best_next_town_so_far = min(u,best_next_town_so_far);
		}
	    max_cost=ZMAX-cur.cost;
		for(int j=0; j<(int)graf[cur.town].size(); j++) { 
		// przetwarzamy wszystkie sasiednie miasta
			int s = graf[u][j].first;
			if (!visited[s]){
				visited[s]= 1;
				next_town.town = s;
				
				next_town.cost = cur.cost + graf[u][j].second;
				if(next_town.cost<=max_cost)
				   queue_push(next_town);
				
				// tu dalszy kod
			}
			// --------tu dalszy kod
		}
	}
	return best_next_town_so_far;
	
}


int a, b, x, m;
LL c, d;
int next_town = 1;



int main() {
	// wczytywanie danych, tworzenie sieci mias i drog
	scanf("%d", &n);  // ilosc miast
	scanf("%d", &q);  // ilosc dni
	for(int i=1; i <= n; i++)  {
		scanf("%lld", Z + i);
		ZMAX=max(ZMAX,Z[i]);
	}
	for(int i=1; i < n; i++)  {
		scanf("%d%d%lld", &a, &b, &c );  // z miasta a do miasta b przejazd kosztuje c
		graf[a].push_back( pair<int, LL>(b, c));
		graf[b].push_back( pair<int, LL>(a, c));  // z b do a tak samo
	}
	// sortowanie listy sasiednich miast, bedziemy z tego korzystac przy ew. zmianach oplat drogowych 
	for(int i=1; i <= n; i++){
		sort(graf[i].begin(),graf[i].end());
	}
	for(int i=1; i <= q; i++)  {
		scanf("%d", &x);
		if(x==1) {
			scanf("%d%lld", &m, &d );
			// zmiana wielkosci sprzedazy w miescie m
			Z[m]= d;
			ZMAX=max(ZMAX, d);
			
		} else {
			scanf("%d%d%lld", &a, &b, &c );
			// zmiana kosztu przejazdu z a do b 
			int l=0;
			int p=graf[a].size()-1;
			int sr;
			while(l<=p){
				sr=(l+p)/2;
				if(b==graf[a][sr].first) break;
				if(b<graf[a][sr].first) p=sr-1;
				else l=sr+1;
			}
			graf[a][sr].second=c;
			
			// i z b do a
			l=0;
			p=graf[b].size()-1;
			while(l<=p){
				sr=(l+p)/2;
				if(a==graf[b][sr].first) break;
				if(a<graf[b][sr].first) p=sr-1;
				else l=sr+1;
			}
			graf[b][sr].second=c;
			
			
		}
		next_town = bfs(next_town);
		printf("%d ", next_town);
		
	}

	return 0;
}