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
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long int lld;

struct graf{
	vector<int> droga;
	int odw;
	lld v;
	lld odl;

	graf(void){
		odw=-1;
	}
};

map<pair<int,int>,lld> m;
graf g[100005];

void bfs(int v, int nr){
	g[v].odl=0;
	g[v].odw=nr;

	queue<int> q;

	q.push(v);

	while(!q.empty()){
		int w=q.front();
		q.pop();

		for(int i=0;i<g[w].droga.size();i++)
			if(g[g[w].droga[i]].odw != nr){
				int u=g[w].droga[i];

				g[u].odw=nr;
				g[u].odl=g[w].odl+m[make_pair(min(w,u),max(w,u))];

				q.push(u);
			}
	}

	return;
}

int main(void){
	int n,q;

	scanf("%d%d",&n,&q);

	for(int i=0;i<n;i++)
		scanf("%lld",&g[i].v);

	for(int i=0;i<n-1;i++){
		int a,b;
		lld v;

		scanf("%d%d%lld",&a,&b,&v);
		a--, b--;

		g[a].droga.push_back(b);
		g[b].droga.push_back(a);
		m[make_pair(min(a,b),max(a,b))]=v;
	}

	int akt=0;

	for(int i=0;i<q;i++){
		int z;

		scanf("%d",&z);

		if(z==1){
			int v;
			lld d;

			scanf("%d%lld",&v,&d);

			g[v-1].v=d;
		}else{
			int a,b;
			lld d;

			scanf("%d%d%lld",&a,&b,&d);

			a--, b--;
			m[make_pair(min(a,b),max(a,b))]=d;
		}

		bfs(akt,i);

		int p=0;
		int a=akt;

		if(akt==0)
			p=1;

		akt=p;
		lld odl=g[p].v-g[p].odl;

		for(lld i=p+1;i<n;i++)
			if(a!=i && g[i].v-g[i].odl > odl){
				odl=g[i].v-g[i].odl;
				akt=i;
			}

		printf("%d ",akt+1);
	}
	printf("\n");
	return 0;
}