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
105
106
107
108
109
110
111
112
113
114
115
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

#define MAX_LL 9000000000000000000LL

#define MAX_N 100000
#define MAX_Q MAX_N

int n, q;
long long Z[MAX_N + 1];
int RES[MAX_Q];
vector<int> E[MAX_N + 1];
vector<long long> EC[MAX_N + 1];
int VISITED[MAX_N + 1];
long long INCOME[MAX_N + 1];

int T[MAX_Q];
int VI[MAX_Q];
int AI[MAX_Q];
int BI[MAX_Q];
long long DI[MAX_Q];

void read();
void write();

void dfs2(int city, long long cost) {
    VISITED[city] = 1;
    INCOME[city] = Z[city] - cost;
    for(int i=0; i<E[city].size(); i++) {
        int v = E[city][i];
        long long d = EC[city][i];
        if(VISITED[v] == 0) dfs2(v, cost + d);
    }
}

int dfs(int city) {
    for(int i=1; i<=n; i++) VISITED[i] = 0;
    VISITED[city] = 1;
    for(int i=0; i<E[city].size(); i++) {
        int v = E[city][i];
        long long d = EC[city][i];
        dfs2(v, d);
    }
    int max_city = -1;
    long long max = MAX_LL;
    for(int i=1; i<=n; i++) {
        if (i == city) continue;
        if (max_city == -1 || INCOME[i] > max) {
            max_city = i;
            max = INCOME[i];
        }
    }
    return max_city;
}

void solve() {
    int city = 1;
    for(int i=0; i<q; i++) {
        if (T[i] == 1) {
            Z[VI[i]] = DI[i];
        } else {
            for(int j=0; j<E[AI[i]].size(); j++) {
                if(E[AI[i]][j] == BI[i]) {
                    EC[AI[i]][j] = DI[i];
                    break;
                }
            }
            for(int j=0; j<E[BI[i]].size(); j++) {
                if(E[BI[i]][j] == AI[i]) {
                    EC[BI[i]][j] = DI[i];
                    break;
                }
            }
        }
        RES[i] = city = dfs(city);
    }
}

int main() {
    read();
    solve();
    write();
    return 0;
}

void read() {
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++) scanf("%lld", &Z[i]);
    for(int i=1; i<n; i++) {
        int a, b;
        long long c;
        scanf("%d %d %lld", &a, &b, &c);
        E[a].push_back(b);
        EC[a].push_back(c);
        E[b].push_back(a);
        EC[b].push_back(c);
    }
    for(int i=0; i<q; i++) {
        scanf("%d", &T[i]);
        if(T[i] == 1) {
            scanf("%d %lld", &VI[i], &DI[i]);
        } else {
            scanf("%d %d %lld", &AI[i], &BI[i], &DI[i]);
        }
    }
}

void write() {
    printf("%d", RES[0]);
    for(int i=1; i<q; i++) printf(" %d", RES[i]);
    printf("\n");
}