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
// Karol Kosinski
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,b) for(int i=1;i<=(b);++i)
//#define DEBUG(x...) printf(x)
#define DEBUG(x...)
using namespace std;

typedef long long LG;
const int NMX = 100003;
int n, q;

struct Edge
{
    LG weight;
    int aim;
};

struct Vertex
{
    LG value;
    vector<Edge> adj;
}
G[NMX];
int Res[NMX];
LG Dist[NMX];

int processQuery(int start)
{
    REP(i,n) Dist[i] = -1;
    Dist[start] = 0;
    stack<int> S;
    S.push(start);
    while (not S.empty())
    {
        int v = S.top();
        S.pop();
        for (const auto& ed : G[v].adj)
        {
            if (Dist[ed.aim] != -1) continue;
            Dist[ed.aim] = Dist[v] + ed.weight;
            S.push(ed.aim);
        }
    }
    int ind = -1;
    LG maxProfit = 0;
    REP(i,n)
    {
        if (i == start) continue;
        LG aux = G[i].value - Dist[i];
        DEBUG("-- [%d] value - dist: %4lld - %4lld = %4lld\n", i, G[i].value, Dist[i], aux);
        if (ind == -1 or maxProfit < aux)
        {
            maxProfit = aux;
            ind = i;
        }
    }
    return ind;
}

int main()
{
    scanf("%d%d", &n, &q);
    REP(i,n)
    {
        int d;
        scanf("%lld", &d);
        G[i].value = d;
    }
    FOR(i,1,n)
    {
        int a, b, c;
        scanf("%d%d%lld", &a, &b, &c);
        G[a].adj.push_back({c, b});
        G[b].adj.push_back({c, a});
    }
    auto cmp = [](const Edge& a, const Edge& b){ return a.aim < b.aim; };
    REP(i,n)
    {
        sort(G[i].adj.begin(), G[i].adj.end(), cmp);
    }
    int currentPosition = 1;
    FOR(i,0,q)
    {
        int k;
        scanf("%d", &k);
        if (k == 1)
        {
            int v, d;
            scanf("%d%lld", &v, &d);
            G[v].value = d;
        }
        else
        {
            int a, b, c;
            scanf("%d%d%lld", &a, &b, &c);
            lower_bound(G[a].adj.begin(), G[a].adj.end(), Edge {0, b}, cmp)->weight = c;
            lower_bound(G[b].adj.begin(), G[b].adj.end(), Edge {0, a}, cmp)->weight = c;
        }
        currentPosition = processQuery(currentPosition);
        DEBUG("** Chosen: %d\n", currentPosition);
        Res[i] = currentPosition;
    }
    FOR(i,0,q) printf("%d ", Res[i]);
    printf("\n");
    return 0;
}