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

const int N = 1e5;
long long profit[N + 1];
pair<int, long long> parent[N + 1];
vector<pair<int, long long> > G[N + 1];
int n, q, currentLocation;
pair<long long, int> best;

void Find(int v, int p, long long dist) {
    if(v != currentLocation)
        if(best.first < profit[v] - dist or (best.first == profit[v] - dist and best.second > v))
            best = make_pair(profit[v] - dist, v);

    int actualParent = parent[v].first;
    for(int i = 0; i < G[v].size(); ++i) {
        int s = G[v][i].first;
        if(s == p)
            continue;
        if(s == actualParent)
            Find(s, v, dist + parent[v].second);
        else
            Find(s, v, dist + parent[s].second);
    }
}

void read() {
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &profit[i]);
    }

    for(int i = 0; i < n - 1; ++i) {
        int a, b;
        long long c;
        scanf("%d%d%lld", &a, &b, &c);
        G[a].push_back(make_pair(b, c));
        G[b].push_back(make_pair(a, c));
    }
}

void dfs(int v, int p) {
    for(int i = 0; i < G[v].size(); ++i) {
        int s = G[v][i].first, cost = G[v][i].second;
        if(s == p)
            continue;
        parent[s] = make_pair(v, cost);
        dfs(s, v);
    }
}

void solve() {
    currentLocation = 1;
    for(int i = 0; i < q; ++i) {
        int command;
        scanf("%d", &command);

        if(command == 1) {
            int v;
            long long d;
            scanf("%d%lld", &v, &d);
            profit[v] = d;
        }
        else {
            int a, b;
            long long d;
            scanf("%d%d%lld", &a, &b, &d);
            if(parent[a].first == b)
                swap(a, b);
            parent[b].second = d;
        }

        best = make_pair(0LL, 0);
        Find(currentLocation, currentLocation, 0LL);
        printf("%d ", best.second);
        currentLocation = best.second;
    }
}

int main()
{
    read();
    dfs(1, 1);
    solve();
    return 0;
}