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
#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i,a,n) for (decltype(n) i = (a), i ## __ = (n); i <= i ## __; ++i)
#define FORD(i,a,n) for (decltype(n) i = (a), i ## __ = (n); i >= i ## __; --i)
#define REP(i,n) FOR(i, 0, n - 1)
#define REPD(i, n) FORD(i, n - 1, 0)
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int(x.size()))
#define EB emplace_back
#define V vector
#define ST first
#define ND second
#define RS resize
 
template<class T, class B> inline void mini(T &&a, B &&b) { if (b < a) a = b; }
template<class T, class B> inline void maxi(T &&a, B &&b) { if (b > a) a = b; }
int ceil2(int x) { return x < 2 ? 1 : 1 << (sizeof(x) * 8 - __builtin_clz(x - 1)); }
 
constexpr char nl = '\n';
template<class T> struct DumpOff { T a, b; };
template<class T> auto dumpOff(T &x) -> DumpOff<decltype(x.begin())> { return {x.begin(), x.end()}; }
template<class T> auto dumpOff(T &x) -> decltype(cerr << x, x) { return x; }
template<class T> auto dumpOff(T &x) -> decltype(x.first, x) { return x; }
struct Debug {
    ~Debug() { cerr << nl; }
    template<class T> auto operator<<(T x) -> decltype(cerr << x, *this) { cerr << dumpOff(x); return *this; }
    template<class T> auto operator<<(T x) -> decltype(x.begin(), *this) {
        cerr << "{\n";
        for (auto a = x.begin(), b = x.end(); a != b; ++a)
            *this << "  " << distance(x.begin(), a) << ": " << dumpOff(*a) << '\n';
        return *this << "}";
    }
    template<class T, class B> Debug& operator<<(pair<T, B> p) { return *this << "(" << dumpOff(p.first) << ", " << dumpOff(p.second) << ")"; }
    template<class T> Debug& operator<<(DumpOff<T> d) {
        cerr << "{";
        for (auto a = d.a, b = d.b; a != b; ++a)
            *this << dumpOff(*a) << (next(a) == b ? "" : ", ");
        return *this << "}";
    }
};
struct Foo {template<class T>Foo& operator<<(T) {return *this;}};
 
#ifdef DEBUG
# define D Debug()
#else
# define D Foo()
#endif
#define I(x...) #x ": " << x << "   "
 

typedef long long LL;
typedef pair<int, int> PII;
typedef V<int> VI;
typedef V<VI> VVI;
typedef V<PII> VPII;
typedef V<VPII> VVPII;
typedef V<bool> VB;
typedef V<VB> VVB;
typedef V<LL> VLL;
typedef V<VLL> VVLL;

VLL w;
V<V<pair<int, LL> > > g;

int a, b;
LL c;
int ans;
LL mx;
LL sum = 0;


void DFS(int v, int p = -1)
{
    if(p != -1) 
    {
        sum += w[v];
        if(sum > mx || (sum == mx && v < ans)) mx = sum, ans = v;
    }    
    REP(i, SZ(g[v]))
    {
        if(g[v][i].ST != p)
        {
            if((v == a && g[v][i].ST == b) || (v == b && g[v][i].ST == a)) g[v][i].ND = c, a = -1, b = -1;
            sum -= g[v][i].ND;
            DFS(g[v][i].ST, v);
            sum += g[v][i].ND;
        }
    }
    if(p != -1) sum -= w[v];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    w.RS(n), g.RS(n);
    REP(i, n) cin >> w[i];
    REP(i, n - 1)
    {
        cin >> a >> b >> c;
        g[a - 1].EB(b - 1, c);
        g[b - 1].EB(a - 1, c);
    }

    REP(i, k)
    {        
        int q;
        cin >> q;
        if(q == 2)
            cin >> a >> b >> c, a--, b--;
        else
        {
            cin >> a >> c;
            w[a - 1] = c;
            a = -1, b = -1;
        }
        mx = -1000000000000000000;
        sum = 0;
        DFS(ans);        
        cout << ans + 1 << " ";
    }
}