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

using namespace std;
const int MAXN = 100000;
const int MAXQ = 100000;
const int PROFIT_CHANGE = 1;
const int COST_CHANGE = 2;
typedef long long int ll;
const ll INF = 1000000000100000000;
typedef pair <int, ll> P;

int n, q;
int a, b;
int current_city = 1;
ll c;
ll city_profit[MAXN + 5];
ll city_cost[MAXN + 5];
bool vis[MAXN + 5];

unordered_map<int,ll> M[MAXN + 5];
unordered_map<int,ll>::iterator it;
int get_city_num();

int main() {
  scanf("%d %d", &n, &q);
  for(int i = 1; i <= n; ++i) {
    scanf("%lld", &city_profit[i]); 
  }
  for(int i = 1; i < n; ++i) {
    scanf("%d %d %lld", &a, &b, &c);
    M[a][b] = c;
    M[b][a] = c;
  }
  for(int i = 0; i < q; ++i) {
    int c_type;
    scanf("%d", &c_type);
    if(c_type == PROFIT_CHANGE) {
      int city;
      ll new_profit;
      scanf("%d %lld", &city, &new_profit);
      city_profit[city] = new_profit;
    } else if(c_type == COST_CHANGE) {
      scanf("%d %d %lld", &a, &b, &c);
      M[a][b] = c;
      M[b][a] = c;
    }
    printf("%d ", get_city_num());
  }
  printf("\n");
  return 0;
}

int get_city_num() {
  for(int i = 1; i <= n; ++i) {
    city_cost[i] = 0LL;
    vis[i] = false;
  }
  queue <int> Q;
  Q.push(current_city);
  P best;
  best.first = -1;
  best.second = -INF;
  vis[current_city] = true;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(it = M[u].begin(); it != M[u].end(); ++it) {
      int v = (*it).first;
      ll road_cost = (*it).second;
      if(!vis[v]) {
        city_cost[v] = city_cost[u] + road_cost;
        ll city_result = city_profit[v] - city_cost[v];
        if(city_result > best.second or (city_result == best.second and v < best.first)) {
          best.first = v;
          best.second = city_result;
        }
        vis[v] = true;
        Q.push(v);
      }
    }
  }

  return current_city = best.first;
}