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<iostream>
#include<vector>
using namespace std;
int n,q,a,b,akcja,poz,w;
long long c;
long long zysk[101000];
vector<pair<int,long long>>graf[101000];
vector<int>kolejka;
int odw[101000];
long long koszt[101000];
long long wynik,y;
int wynpoz,x;
long long wyniczek;
#ifdef _WIN32
#define getc_unlocked getc
#endif // _WIN32
inline void read(int *n){
    register char c = 0;
    while (c < 33) c=getc_unlocked(stdin);
    (*n) = 0;
    while (c>32) {(*n)=(*n)*10LL + (c-48); c=getc_unlocked(stdin);}
}
inline void read(long long *n){
    register char c = 0;
    while (c < 33) c=getc_unlocked(stdin);
    (*n) = 0;
    while (c>32) {(*n)=(*n)*10LL + (c-48); c=getc_unlocked(stdin);}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    read(&n);
    read(&q);
    //cin>>n>>q;
    for(int i=1;i<=n;++i){
        read(&zysk[i]);
        //cin>>zysk[i];
    }
    for(int i=0;i<n-1;++i){
        read(&a);
        read(&b);
        read(&c);
        //cin>>a>>b>>c;
        graf[a].push_back(make_pair(b,c));
        graf[b].push_back(make_pair(a,c));
    }
    poz=1;
    for(int i=0;i<q;++i){
        read(&akcja);
        //cin>>akcja;
        if(akcja==1){
            read(&a);
            read(&c);
            //cin>>a>>c;
            zysk[a]=c;
        }
        else if(akcja==2){
            read(&a);
            read(&b);
            read(&c);
            //cin>>a>>b>>c;
            for(int j=0;j<graf[a].size();++j){
                if(graf[a][j].first==b){
                    graf[a][j].second=c;
                    break;
                }
            }
            for(int j=0;j<graf[b].size();++j){
                if(graf[b][j].first==a){
                    graf[b][j].second=c;
                    break;
                }

            }
        }
        for(int j=1;j<=n;++j){
            odw[j]=0;
        }
        wynik=-9000000000000000000;
        wynpoz=1;
        koszt[poz]=0;
        kolejka.push_back(poz);
        odw[poz]=1;
        for(int j=0;j<kolejka.size();++j){
            w=kolejka[j];
            for(int k=0;k<graf[w].size();++k){
                x=graf[w][k].first;
                y=graf[w][k].second;
                if(!odw[x]){
                    odw[x]=1;
                    koszt[x]=koszt[w]+y;
                    kolejka.push_back(x);
                    wyniczek=zysk[x]-koszt[x];
                    if(wyniczek>wynik||(wyniczek==wynik&&x<wynpoz)){
                        wynik=wyniczek;
                        wynpoz=x;
                    }
                }
            }
        }
        poz=wynpoz;
        cout<<poz<<" ";
    }
}