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
#include<vector>
#include<cstdio>

#include<utility>
#define N 100001

using namespace std;

struct road {
	int destination;
	long long int price;
};

long long int tab[N];
vector<road> cities[N];

pair<int, long long int> search(int v1, int v2, long long int sum)
{
	pair<int, long long int> pr;	
	bool set = (v2 == -1);
	pr.second = tab[v1] - sum;
	

	pr.first = v1;
	
	for(const road& r : cities[v1]) {
		if(r.destination != v2) {
			auto d = search(r.destination, v1, sum + r.price);
			if(set || d.second > pr.second || (d.second == pr.second && d.first < pr.first)) {
				pr = d;
			}
		}
	}
	return pr;
}

int main()
{
	int n;
	scanf("%d", &n);
	int q;
	scanf("%d", &q);
	
	for(int i = 0; i < n; i++){
		scanf("%lld", &tab[i+1]);
	}


	int start = 1;
	
	for(int i = 1; i<n; i++) {
		int start;
		scanf("%d", &start);
		int dest;
		scanf("%d", &dest);
		long long int cost;
		scanf("%lld", &cost);
		
		cities[start].push_back({dest, cost});
		cities[dest].push_back({start, cost});
	}
	
    int city = start;
	for(int a_1 = 0; a_1<q; a_1++){
		int mode;
		scanf("%d", &mode);

		if (mode == 2) {
			int city1;
			scanf("%d", &city1);
			int city2;
			scanf("%d", &city2);
			
			long long int cost;
			scanf("%lld", &cost);
			
			
			for(road& cty : cities[city1]) {
				if(cty.destination == city2) {
					cty.price = cost;
					break;
				}
			}
			
			
			for(road& cty : cities[city2]){
				if(cty.destination == city1)	{
					cty.price = cost;
					break;
				}
			}			
		} else if(mode == 1) {
			int city;
			scanf("%d", &city);
			scanf("%lld", &tab[city]);			
		}
		
		
		auto c = search(city, -1, 0);
		printf("%d ", c.first);
		city = c.first;
	}
	
	
	printf("\n");
	
	return 0;
}