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
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int kMaxNumberOfCities = 100000;


struct Road {
    Road(int dest, long long c) : destination(dest), cost(c) {}
    long long cost;
    int destination;
};

class City {
public:
    void changeDestinationCost(int dest, long long cost) {
        for ( vector<Road>::iterator it = destinations.begin(); it != destinations.end(); it++ ) {
            if ( (*it).destination == dest ) {
                (*it).cost = cost;
                break;
            }
        }
    }
    long long profit;
    long long trip_cost;
    vector<Road> destinations;
};

City cities[kMaxNumberOfCities + 1];
int current_city;
int n, q;

int findNextCity() {
    int next_city = -1;
    long long earn = -922337203685477580ll;
    bool visitedCity[n+1];
    for ( int i = 1; i <= n; i++ )
        visitedCity[i] = false;
    std::queue<City> queue;
    cities[current_city].trip_cost = 0;
    queue.push(cities[current_city]);
    visitedCity[current_city]=true;
    while ( !queue.empty() ) {
        long long tmp_earn;
        City city = queue.front();
        queue.pop();
        for ( int i =0; i < city.destinations.size(); i++ ) {
            int dest = city.destinations[i].destination;
            if ( visitedCity[dest])
                continue;
            visitedCity[dest] = true;
            City c = cities[dest];
            c.trip_cost = city.trip_cost + city.destinations[i].cost;
            tmp_earn = c.profit - c.trip_cost;
            queue.push(c);
            if ( tmp_earn > earn ) {
                next_city = dest;
                earn = tmp_earn;
            }
            else if ( tmp_earn == earn )
                if ( next_city > dest )
                    next_city = dest;
        }
    }
    return next_city;
}

int main(int argc, const char * argv[]) {
    current_city = 1;
    cin >> n >> q;
    for ( int i = 1; i <= n; i++ )
        cin >> cities[i].profit;
    int c = n;
    while ( --c ) {
        int a, b;
        long long cost;
        cin >> a >> b >> cost;
        cities[a].destinations.push_back(Road(b, cost));
        cities[b].destinations.push_back(Road(a, cost));
    }
    
    while ( q-- ) {
        short option;
        cin >> option;
        if ( option == 1 ) {
            int city;
            cin >> city;
            cin >> cities[city].profit;
        } else {
            int a, b;
            long long cost;
            cin >> a >> b >> cost;
            cities[a].changeDestinationCost(b, cost);
            cities[b].changeDestinationCost(a, cost);
        }
        current_city = findNextCity();
        cout << current_city << " ";
    }
    return 0;
}