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
// Lupus Nocawy 26 XI 2017, PA2017
// http://potyczki.mimuw.edu.pl/
// Runda 5
// Zadanie: BAN
// Banany [B]

#include <cstdio>
#include <algorithm>
#include <vector>
#include <list>
#include <cmath>
using namespace std;
#define REP(i,n) for(int i=0, _n=n; i<_n; ++i)
#define FOR(i,a,b) for(int i=(a), _b=(b); i<=_b; ++i)
#define IT(i,x) __typeof__(x) i=x
#define MP make_pair
#define PB push_back
typedef long long int lli;
typedef unsigned long long int llu;
typedef pair<int,int> pii;
const int debug=0;

const int INF = 2147483647;
const lli INFm = -9223372036854775807;
const int max_n = 100000; // 10^5`
const int max_q = 100000; // 10^5`

struct edge{
	int a;	// this
	int b;	// next
	lli c;	// cost
	edge(int a, int b, lli c): a(a), b(b), c(c) {};
};

vector<edge> E[max_n+1];
lli z[max_n+1];
lli profit[max_n+1];
int visited[max_n+1];

void addEdge(int a, int b, lli c){
	E[a].PB(edge(a,b,c));
	E[b].PB(edge(b,a,c));
}

void updateEdge(int a, int b, lli d){
	for(auto &it : E[a]){
		if(it.b == b){
			it.c = d;
			break;
		}
	}
	for(auto &it : E[b]){
		if(it.b == a){
			it.c = d;
			break;
		}
	}
}

void DFSr(int x, lli cost){
	for(auto &it : E[x]){
		int b = it.b;
		if(not visited[b]){
			profit[b] = z[b] - cost - it.c;
			visited[b] = 1;
			DFSr(b, cost + it.c);
		}
	}
}

int DFS(int x, int n){
	FOR(i,1,n)
		visited[i] = 0;

	profit[x] = INFm;
	visited[x] = 1;
	DFSr(x, 0);	// node, cost

	int r = 1;	// result, max profit index
	FOR(i,2,n){
		if(profit[i] > profit[r])
			r = i;
	}
	return r;
}

int main(void){
	int n,q;
	scanf("%d %d ", &n, &q);
	FOR(i,1,n){
		scanf("%lli ", z+i);
	}
	FOR(i,1,n-1){
		int a,b;
		lli c;
		scanf("%d %d %lli ", &a, &b, &c);
		addEdge(a,b,c);
	}

	int x = 1;
	FOR(i,1,q){
		int T;
		scanf("%d ", &T);

		if(T==1){
			int v;
			lli d;
			scanf("%d %lli ", &v, &d);
			z[v] = d;
		}

		else /*t==2*/{
			int a, b;
			lli d;
			scanf("%d %d %lli ", &a, &b, &d);
			updateEdge(a,b,d);
		}

		x = DFS(x,n);
		printf("%d ", x);
	}
	printf("\n");

	return 0;
}