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
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef long long ll;
vector<pair<int, ll>> adj[MAXN];
int v, q, a, b;
ll w;
ll ceny[MAXN];
ll odleglosc[MAXN];

int znajdz(int poz) {
  for(int i = 0; i < v; i++) {
    odleglosc[i] = -1ll;
  }
  odleglosc[poz] = 0;
  queue<int> kol;
  kol.push(poz);
  while(!kol.empty()) {
    int x = kol.front();
    kol.pop();
    for(int i = 0; i < adj[x].size(); i++) {
      if (odleglosc[adj[x][i].first] == -1ll) {
        odleglosc[adj[x][i].first] = odleglosc[x] + adj[x][i].second;
        kol.push(adj[x][i].first);
      }
    }
  }
  int best = -1;
  ll value = -1000000000000000000ll;
  for(int i = 0; i < v; i++){
    if (i == poz) continue;
//    printf("c o %lld %lld value %lld\n", ceny[i], odleglosc[i], value);
//    printf("%lld %lld %lld\n", ceny[i] - odleglosc[i], value, ceny[i] - odleglosc[i] > value);
    if ((ceny[i] - odleglosc[i]) > value) {
//      printf("c o %d %d\n", ceny[i], odleglosc[i]);
      best = i;
      value = ceny[i] - odleglosc[i];
    }
  }
//  printf("%d\n", value);
  return best;
}
int main(){
  scanf("%d%d", &v, &q);
  for(int i = 0; i < v; i++) scanf("%lld", &ceny[i]);
  for(int i = 0; i < v - 1; i++){
    scanf("%d%d%lld", &a, &b, &w);
    a--;b--;
    adj[a].push_back(make_pair(b,w));
    adj[b].push_back(make_pair(a,w));
  }
  for(int i = 0; i < v; i++)
    sort(adj[i].begin(), adj[i].end());
  int pozycja = 0;
  while(q--){
    int t;
    ll z;
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d%lld", &a, &z);
      a--;
//      printf("zmienilem cene %d ", a);
      ceny[a] = z;
    } else {
      scanf("%d%d%lld", &a, &b, &w);
      a--; b--;
      *lower_bound(adj[a].begin(), adj[a].end(), make_pair(b, -1ll)) = make_pair(b, w);
      *lower_bound(adj[b].begin(), adj[b].end(), make_pair(a, -1ll)) = make_pair(a,w);
//      printf("zmienilem %d na ", a);
//      for(int i = 0; i < adj[a].size(); i++){ printf("(%d %d)", adj[a][i].first, adj[a][i].second);}
//      printf("\n");
    }
    int najlepsze = znajdz(pozycja);
    printf("%d ", najlepsze+1);
    pozycja = najlepsze;
  }
  printf("\n");
}