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
#include<bits/stdc++.h>

using namespace std;

vector<pair<int,long long> >graf[100007];
long long tab[100007];
bool odwiedzony[100007];
long long roznica[100007];

queue<int>q;
long long odleglosc[100007];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	long long x,y,z,o;
	for(int a=1;a<=n;a++)
		cin>>tab[a];
	for(int a=0;a<n-1;a++)
	{
		cin>>x>>y>>z;
		graf[x].push_back(make_pair(y,z));
		graf[y].push_back(make_pair(x,z));
	}
	int poprzedni=1;
	for(int b=0;b<m;b++)
	{
		cin>>x>>y>>z;
		if(x==1)
		{
			tab[y]=z;
		}
		else
		{
			cin>>o;
			int a=0;
			while(graf[y][a].first!=z)
			{
				a++;
			}
			graf[y][a]=make_pair(z,o);
			a=0;
			while(graf[z][a].first!=y)
			{
				a++;
			}
			graf[z][a]=make_pair(y,o);
		}
		
		for(int a=0;a<=n;a++)
		{
			odwiedzony[a]=0;
			odleglosc[a]=1000000000000000001;
			if(poprzedni==a)
			{
				odleglosc[a]=0;
			}
		}
		q.push(poprzedni);
		odwiedzony[poprzedni]=1;
		while(!q.empty())
		{
			int w=q.front();
			q.pop();
			for(int a=0;a<graf[w].size();a++)
			{
				if(odwiedzony[graf[w][a].first]==0)
				{
					q.push(graf[w][a].first);
					odleglosc[graf[w][a].first]=odleglosc[w]+graf[w][a].second;
					odwiedzony[graf[w][a].first]=1;
				}
			}
			
		}
		long long ma=-1000000000000000001,nr=0;
		for(int a=1;a<=n;a++)
		{
			roznica[a]=tab[a]-odleglosc[a];
			if(ma<roznica[a]&&a!=poprzedni)
			{
				ma=roznica[a];
				nr=a;	
				
			}
			//cout<<odleglosc[a]<<" ";
		}
		cout<<nr<<" ";
		poprzedni=nr;
	}
	
}