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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <vector>

using namespace std;


struct possible_move {
    possible_move(int64_t p, int64_t id) {
        price_of_move = p;
        city_id = id;
    }

    int64_t city_id;
    int64_t price_of_move;
};

struct City {
    int64_t price;
    int64_t city_number;
    vector<possible_move> moves;
    bool used = false;
};

struct Changes_price {
    int64_t new_price, id_city, id_destiny;
    int type;
};


int main() {
    int64_t n, q;
    cin >> n >> q;
    vector<City> graph(n + 1);
    vector<Changes_price> change_prices(q + 1);
    vector<int64_t> output;
    for (int64_t count = 1; count <= n; count++) {
        int64_t temp_price;
        cin >> temp_price;
        City temp;
        temp.city_number = count;
        temp.price = temp_price;
        graph[count] = temp;
    }
    for (int64_t count = 0; count < n - 1; count++) {
        int64_t from_id;
        int64_t destination_id;
        int64_t price;
        cin >> from_id >> destination_id >> price;
        possible_move temp(price, destination_id);
        possible_move temp2(price, from_id);
        graph[from_id].moves.push_back(temp);
        graph[destination_id].moves.push_back(temp2);
    }
    for (int64_t count = 1; count <= q; count++) {
        int type;
        cin >> type;
        if (type == 1) {
            int64_t id;
            int64_t price;
            cin >> id >> price;
            Changes_price temp;
            temp.type = type;
            temp.new_price = price;
            temp.id_city = id;
            temp.id_destiny = 0;
            change_prices[count] = temp;
        } else if (type == 2) {
            int64_t from_id;
            int64_t destination_id;
            int64_t price;
            cin >> from_id >> destination_id >> price;
            Changes_price temp;
            temp.type = type;
            temp.new_price = price;
            temp.id_city = from_id;
            temp.id_destiny = destination_id;
            change_prices[count] = temp;
        }
    }
    int64_t current_city = 1, last_city = 1, start_city = 1;
    for (int count = 1; count <= q; count++) {
        Changes_price change = change_prices[count];
        if (change.type == 1) {
            graph[change.id_city].price = change.new_price;
            //cout << "New price in city " << change.id_city << " = " << graph[change.id_city].price << '\n';
        } else if (change.type == 2) {
            vector<possible_move> city1 = graph[change.id_city].moves;
            vector<possible_move> city2 = graph[change.id_destiny].moves;
            for (int64_t count1 = 0; count1 < city1.size(); count1++) {
                if (city1[count1].city_id == change.id_destiny) {
                    city1[count1].price_of_move = change.new_price;
                    graph[change.id_city].moves = city1;
                    //cout << "New price from city " << change.id_city << " to city " << change.id_destiny << " = "
                    //     << graph[change.id_city].moves[count1].price_of_move << '\n';
                }
            }
            for (int64_t count1 = 0; count1 < city2.size(); count1++) {
                if (city2[count1].city_id == change.id_city) {
                    city2[count1].price_of_move = change.new_price;
                    graph[change.id_destiny].moves = city2;
                   // cout << "New price from city " << change.id_destiny << " to city " << change.id_city << " = "
                     //    << graph[change.id_destiny].moves[count1].price_of_move << '\n';
                }
            }
        }
        int64_t balance = 0;
        int64_t move_balance =
                graph[graph[start_city].moves[0].city_id].price - graph[start_city].moves[0].price_of_move;
       // cout << move_balance << '\n';
        current_city = graph[start_city].moves[0].city_id;
        for (int64_t count1 = 0; count1 < graph[start_city].moves.size(); count1++) {
            if (move_balance < graph[graph[last_city].moves[count1].city_id].price -
                               graph[last_city].moves[count1].price_of_move and
                graph[last_city].moves[count1].city_id != start_city) {
                move_balance = graph[graph[last_city].moves[count1].city_id].price -
                               graph[current_city].moves[count1].price_of_move;
                current_city = graph[last_city].moves[count1].city_id;
            }
           // cout << "in " << move_balance << '\n';
        }
        balance += move_balance;

        while (last_city != current_city) {
            last_city = current_city;
            if (graph[last_city].moves.size() > 1 and graph[current_city].used==false) {
                move_balance = graph[graph[last_city].moves[0].city_id].price - graph[last_city].moves[0].price_of_move;
                int64_t size = graph[last_city].moves.size();
                for (int64_t count1 = 0; count1 < size; count1++) {
                    if(graph[current_city].moves[count1].city_id==last_city){
                        continue;
                    }
                    if (move_balance <= graph[graph[last_city].moves[count1].city_id].price -
                                       graph[last_city].moves[count1].price_of_move and
                        graph[last_city].moves[count1].city_id != start_city) {
                        move_balance = graph[graph[last_city].moves[count1].city_id].price -
                                       graph[current_city].moves[count1].price_of_move;
                        current_city = graph[last_city].moves[count1].city_id;
                        graph[last_city].used = true;
                    }
                }
            }
            //cout << move_balance << '\n';
            if(balance<move_balance){
                balance = move_balance;
            }
            else break;

        }
        for(int64_t count2 = 1; count2 <= graph.size(); count2++){
            graph[count2].used = false;
        }
        output.push_back(last_city);
        start_city = last_city;
    }
    for (int64_t count = 0; count < output.size(); count++) {
        cout << output[count] << " ";
    }
    cout << '\n';
    return 0;
}