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

#define st first
#define nd second

const long long INF = 1000000000000000000LL;

int n, q, p;

long long tab [100007];
vector < pair < int, long long > > graf [100007];

pair < long long, int > maxi;

bool m( pair < long long , int > a, pair < long long , int > b){
    if(a.st == b.st)
        return a.nd > b.nd;
    return a.st < b.st;
}

void dfs(int u, int mat, long long int suma){

    if(u != mat){
        if( m(maxi, {(suma + tab[u]), u}) )
            maxi =  {(suma + tab[u]), u};
    }

    for(auto w : graf[u]){
        if(w.st == mat){
            continue;
        }

        dfs(w.st, u, suma - w.nd);
    }

    return;
}

void f(){
    maxi = {-INF, -INF};

    dfs(p, p, 0LL);

    p = maxi.nd;
    return;
}

int main(){
    scanf("%d %d",&n,&q);

    for(int i = 1;i <= n; i++){
        scanf("%lld",&tab[i]);
    }

    for(int i = 1;i < n; i++){
        int a, b;
        long long int c;
        scanf("%d %d %lld",&a,&b,&c);

        graf[a].push_back({b,c});
        graf[b].push_back({a,c});
    }
    p = 1;

    int x;
    for(int j = 1;j <= q; j++){
        scanf("%d",&x);

        if(x == 1){
            int v;
            long long int d;
            scanf("%d %lld",&v,&d);

            tab[v] = d;
        }
        else{
            int a, b;
            long long int d;
            scanf("%d %d %lld",&a,&b,&d);

            for(int i = 0;i < graf[a].size(); i++){
                if(graf[a][i].st == b){
                    graf[a][i].nd = d;
                    break;
                }
            }
            for(int i = 0;i < graf[b].size(); i++){
                if(graf[b][i].st == a){
                    graf[b][i].nd = d;
                    break;
                }
            }

        }

        f();
        printf("%d ",p);
    }

    return 0;
}