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
#include <bits/stdc++.h>

using namespace std;

int n, q;
vector<pair<int, long long> > g[100005];
long long odl[100005];
long long wart[100005];

int dfs(int v, long long od, int oj) {
    odl[v]=od-wart[v];
    for(int i=0; i<g[v].size(); i++) {
        if(g[v][i].first!=oj) {
            dfs(g[v][i].first, od+g[v][i].second, v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        cin >> wart[i];
    }
    for(int i=0; i<n-1; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,c));
    }
    // cout << "\n";
    int now = 1;
    for(int i=0; i<q; i++) {
        long long a;
        cin >> a;
        if(a==1) {
            long long b, c;
            cin >> b >> c;
            wart[b]=c;
        }
        if(a==2) {
            long long b, c, d;
            cin >> b >> c >> d;
            int rem, rem2;
            for(int j=0; j<g[b].size(); j++) {
                if(g[b][j].first == c) {
                    rem = j;
                }
            }
            for(int j=0; j<g[c].size(); j++) {
                if(g[c][j].first == b) {
                    rem2 = j;
                }
            }
            g[b][rem].second=d;
            g[c][rem2].second=d;
        }
        // cout << "asdfasdfasdf\n";
        // for(int i=1; i<=n; i++) {
        //     cout << i << ":\n";
        //     for(int j=0; j<g[i].size(); j++) {
        //         cout << g[i][j].first << " " << g[i][j].second << "\n";
        //     }
        // }
        dfs(now, 0, 0);
        // for(int i=1; i<=n; i++) {
        //     cout << i << " - " << odl[i] << "\n";
        // }
        int id=-1;
        long long mini = 9223372036854775807;
        for(int j=1; j<=n; j++) {
            if(j!=now && odl[j]<mini) {
                mini=odl[j];
                id=j;
            }
        }
        now = id;
        cout << id << " ";
    }
}