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
#include <cstdio>
#include <vector>
#include <algorithm>
#define LL long long
using namespace std;

struct _node{
  LL waga;
  int index;
  _node(int index, LL waga){
    this->waga = waga;
    this->index = index;
  }
  _node(){}
  bool operator<(const _node & aaa)const{
    return this->index<aaa.index;
    //return 0;
  }
  bool operator<(const int & aaa)const{
    return this->index<aaa;
    //return 0;
  }
};
vector<_node> graf[120000];
vector<_node>::iterator it;

int n,q;
LL zarobione[120000];

bool visited[120000];
LL makszysk;
int maksindex;

void cleardfs(){
  makszysk = -1e18;
  for(int i=0; i<=n+1; i++){
    visited[i] = false;
  }
}
void DFS(int s,LL cenadrogi){
  visited[s] = true;
  for(int i=0; i<graf[s].size(); i++){
    if(!visited[graf[s][i].index]){
      if(zarobione[graf[s][i].index]-(cenadrogi+graf[s][i].waga)>=makszysk){
        if(zarobione[graf[s][i].index]-(cenadrogi+graf[s][i].waga)==makszysk){
          if(maksindex>graf[s][i].index){
            makszysk = zarobione[graf[s][i].index]-(cenadrogi+graf[s][i].waga);
            maksindex = graf[s][i].index;
          }
        }
        else{
          makszysk = zarobione[graf[s][i].index]-(cenadrogi+graf[s][i].waga);
          maksindex = graf[s][i].index;
        }
      }
      DFS(graf[s][i].index,cenadrogi+graf[s][i].waga);
    }
  }
}

int main(){
  scanf("%d%d",&n,&q);
  for(int i=1; i<=n; i++){
    LL temp;
    scanf("%lld",&temp);
    zarobione[i] = temp;
  }
  for(int i=1; i<n; i++){
    int a,b;
    LL waga;
    scanf("%d%d%lld",&a,&b,&waga);
    graf[a].emplace_back(b,waga);
    graf[b].emplace_back(a,waga);
  }
  for(int i=1; i<n; i++){
    sort(graf[i].begin(),graf[i].end());
  }
  int curindex = 1;
  for(int i=1; i<=q; i++){

    int typ;
    scanf("%d",&typ);
    if(typ==1){
      int v;
      LL d;
      scanf("%d%lld",&v,&d);
      zarobione[v] = d;
    }
    else{//2
      int a,b;
      LL waga;
      scanf("%d%d%lld",&a,&b,&waga);
      it = lower_bound(graf[a].begin(),graf[a].end(),b);
      it->waga = waga;
      it = lower_bound(graf[b].begin(),graf[b].end(),a);
      it->waga = waga;
    }
    cleardfs();
    DFS(curindex,(long long)(0));
    curindex = maksindex;
    printf("%d ",curindex);
  }

}