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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>

using namespace std;

struct Edge {
    int to;
    long long cost;

};
bool operator<(const Edge& lhs, const Edge& rhs) {
    return (lhs.to < rhs.to);
}

int actual_node = 1;
int n, q;
vector<long long> gains;
vector<set<Edge>> edges;

vector<long long> costs;

void read() {
    scanf("%d%d", &n, &q);
    edges.resize(n+1);
    gains.resize(n+1);
    costs.resize(n+1);

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

        int from;
        scanf("%d%d%lld", &from, &now.to, &now.cost);

        edges[from].insert(now);

        swap(from, now.to);

        edges[from].insert(now);
    }
}


void find_costs(int node) {
//    printf("DFS node %d, cost %d\n", node, cost);
    for(auto next: edges[node]) {
        if (costs[next.to] == -1) {
            costs[next.to] = costs[node] + next.cost;
            find_costs(next.to);
        }
    }
}

void find_costs() {
    std::fill(costs.begin(), costs.end(), -1);
    costs[actual_node] = 0;
    find_costs(actual_node);
}

void find_best() {
//    printf("Iteration. Actual node = %d\n", actual_node);
    find_costs();

    // -delta, node
    vector<pair<long long, int>> delta;

    for(int i = 1; i <= n; ++i) {
//        printf("[%d]: %d %d\n", i, costs[i], gains[i] - costs[i]);
        if (i == actual_node)
            continue;
        delta.push_back(make_pair(costs[i]-gains[i], i));
    }

    std::sort(delta.begin(), delta.end());

//    for(auto i : delta) {
//        printf ("%lld %d\n", -i.first, i.second);
//    }

//    printf("Actual night in %d, gain %lld\n", delta[0].second, -delta[0].first);
    actual_node = delta[0].second;
}

int main() {
    read();

    for(int _ = 0; _ < q; ++_) {
        int operation;
        scanf("%d", &operation);
//        printf("Operation %d\n", operation);
        if (operation == 1) {
            int node;
            long long val;
            scanf("%d%lld", &node, &val);
            gains[node] = val;
        }
        if (operation == 2) {
            Edge update;

            int from, to;
            scanf("%d%d%lld", &from, &to, &update.cost);

//            printf("Update cost (%d %d): %d\n", from, to, update.cost);

            update.to = to;
            auto search = edges[from].find(update);
            assert(search != edges[from].end());
            edges[from].erase(search);
            edges[from].insert(update);


            update.to = from;
            search = edges[to].find(update);
            assert(search != edges[to].end());
            edges[to].erase(search);
            edges[to].insert(update);
        }

        find_best();
        printf("%d ", actual_node);
    }
    printf("\n");
    return 0;
}