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<stdio.h>
#include<map>
#include<set>
#include<vector>
using namespace std;
long long zyski[100100];
long long max_zysk = 0;
long long koszt_dojscia[100100];
map<int,long long> koszty[100100];
int najlepsze;
vector<int> sasiedzi[100100];
void policz(int m, int p, long long koszt)
{
	koszt_dojscia[m]=koszt;
	if(najlepsze == 0 || zyski[m]-koszt_dojscia[m] > zyski[najlepsze] - koszt_dojscia[najlepsze] ||
			zyski[m]-koszt_dojscia[m] == zyski[najlepsze] - koszt_dojscia[najlepsze] && m<najlepsze)
		najlepsze = m;

	if(max_zysk-koszt < zyski[najlepsze] - koszt_dojscia[najlepsze])return;
	for(auto v : sasiedzi[m])
	{
		if(v!=p)
			policz(v,m,koszty[v][m] + koszt);
	}
}

int najzyskowniejsze(int m, int n)
{
	for(int i=1;i<=n;i++)
	{
		koszt_dojscia[i]=1100000000000000000LL;
	}
	koszt_dojscia[m]=0;
	najlepsze=0;
	for(auto v : sasiedzi[m])
	{
		policz(v,m,koszty[v][m]);
	}

	/*
        printf("najzyskowniejsze(%d)\n",m);

	for(int i = 1;i<=n;i++)
        {
                printf("zyski[%d]=%lld\n",i,zyski[i]);
        }
	for(auto it: koszty)
	{
		printf("koszty[%d,%d]=%lld\n",it.first.first,it.first.second,it.second);
	}
	for(int i = 1;i<=n;i++)
	{
		printf("koszt_dojscia[%d]=%lld\n",i,koszt_dojscia[i]);
	}
*/
	return najlepsze;
}

int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",zyski+i);
		if(zyski[i]>max_zysk)max_zysk = zyski[i];
	}
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		long long k;
		scanf("%d%d%lld",&a,&b,&k);
		koszty[a][b] = k;
		koszty[b][a] = k;
		sasiedzi[a].push_back(b);
		sasiedzi[b].push_back(a);
	}
	int city = 1;
	for(int i=0;i<q;i++)
	{
		int t;
		scanf("%d",&t);
		if(t==1)
		{
			int m;
			long long z;
			scanf("%d%lld",&m,&z);
			zyski[m]=z;
		} else {
			int a,b;
			long long k;
			scanf("%d%d%lld",&a,&b,&k);
			koszty[a][b]=k;
			koszty[b][a]=k;
		}
		city = najzyskowniejsze(city, n);
		printf("%d ",city);
	}
	return 0;
}