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
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <string>
#include <assert.h>

using namespace std;
typedef long long int llint;

/*

4 4
10 20 30 50
1 2 5
2 3 7
2 4 57
1 3 28
1 1 25
2 3 2 1
2 2 4 13

*/

vector<llint> c;
vector<unordered_map<int, llint>> l;

int best;
llint bestc;
vector<bool> vis;

void go(int x,llint sumc)
{
	const auto& m=l[x];
  for(auto it=m.begin();it!=m.end();++it)
  {
  	int v=it->first;
  	if(vis[v])continue;
  	vis[v]=true;
  	llint cost=sumc+c[v]-it->second;
  	if(best==-1||
  	  cost>bestc||
  	  (cost==bestc&&v<best))
  	{
  		best=v;
  		bestc=cost;
  	}
  	go(v,sumc-it->second);
  }
}

int main()
{
	int n,q;
	cin>>n>>q;
	c.resize(n);
	for(int i=0;i<n;++i)
	  cin>>c[i];
	l.resize(n);
	for(int i=0;i<n-1;++i)
	{
		int a,b;
		llint c;
		cin>>a>>b>>c;
		l[a-1][b-1]=c;
		l[b-1][a-1]=c;
	}
	int x=0;
	vis.resize(n);
	for(int i=0;i<q;++i)
	{
		int t;
	    cin>>t;
	    if(t==1)
	    {
	    	int v;
	    	llint d;
	    	cin>>v>>d;
	    	c[v-1]=d;
	    }
	    else
	    {
	    	int a,b;
	    	llint d;
	    	cin>>a>>b>>d;
	    	l[a-1][b-1]=d;
	    	l[b-1][a-1]=d;
	    }
	    for(int j=0;j<n;++j)
	      vis[j]=false;
	    best=-1;
	    vis[x]=true;
	    go(x,0);
	    cout<<((x=best)+1)<<" ";
	}

	return 0;
}