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
#include<cstdio>
#include<vector>
#include<map>
#include<utility>
#include<algorithm>
#include<climits>

using namespace std;

pair<int, long long> find_best_dest(int prev_city, int start_city,
	vector<long long>& cities, vector<map<int, long long> >& edges) {
    //printf("Starting with: %d, %d\n", prev_city, start_city); 
    long long best_income = LLONG_MIN;
    int best_dest = -1;
    for (map<int, long long>::iterator it = edges[start_city].begin();
	    it != edges[start_city].end(); ++it) {
	int city = it->first;
	//printf("Checking next city: %d\n", city);
	if (city != prev_city) {
	    long long cost = it->second;
	    long long city_income = cities[city] - cost;
	    //printf("City income: %lld\n", city_income);
	    if (city_income > best_income || (city_income == best_income &&
		    city < best_dest)) {
		best_dest = city;
		best_income = city_income;
	    }
	    pair<int, long long> city_result = find_best_dest(start_city,
		city, cities, edges);
	    //printf("City %d result: <%d, %lld>\n", city, city_result.first, city_result.second);
	    long long candidate_res = city_result.second - cost;
	    if (city_result.first != -1 && (candidate_res > best_income ||
		    (candidate_res == best_income && city_result.first < best_dest))) {
		best_dest = city_result.first;
		best_income = candidate_res;
	    }
	}
    }

    //printf("Result for start city %d: <%d, %lld>\n", start_city, best_dest, best_income);

    return make_pair(best_dest, best_income);
}

int main() {
    int n, q;
    scanf("%d %d\n", &n, &q);
    vector<long long> cities(n);
    for (int i = 0; i < n; i++) {
	scanf("%lld", &cities[i]);
    }

    vector<map<int, long long> > edges;
    for (int i = 0; i < n; i++) {
	map<int, long long> tmp_map;
	edges.push_back(tmp_map);
    }

    for (int i = 0; i < n - 1; i++) {
	int city_a, city_b;
	long long cost;
	scanf("%d %d %lld\n", &city_a, &city_b, &cost);
	edges[city_a - 1][city_b - 1] = cost;
	edges[city_b - 1][city_a - 1] = cost;
    }

    int curr_city = 0;
    for (int i = 0; i < q; i++) {
	int type;
	scanf("%d", &type);
	if (type == 1) {
	    int city;
	    long long income;
	    scanf("%d %lld\n", &city, &income);
	    cities[city - 1] = income;
	} else {
	    int city_a, city_b;
	    long long cost;
	    scanf("%d %d %lld\n", &city_a, &city_b, &cost);
	    edges[city_a - 1][city_b - 1] = cost;
	    edges[city_b - 1][city_a - 1] = cost;
	}

	pair<int, long long> res = find_best_dest(curr_city, curr_city,
	    cities, edges);
	curr_city = res.first;
	printf("%d", curr_city + 1);
	printf(i < q - 1 ? " " : "\n");
    }

    return 0;
}