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
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

vector < int > G[ 100001 ];
vector < long long > D[ 100001 ];
long long tab[ 100001 ];
long long maks;
int id;

void change( int x, int y, long long z )
{
    int left = 0, mid, right = G[ x ].size();
    while ( true )
    {
        if ( left == right )
        {
            G[ x ].insert( G[ x ].begin() + left, y );
            D[ x ].insert( D[ x ].begin() + left, z );
            return;
        }

        mid = ( left + right ) / 2;

        if ( y == G[ x ][ mid ] )
        {
            D[ x ][ mid ] = z;
            return;
        }

        if ( y < G[ x ][ mid ] ) right = mid;
        else left = mid + 1;
    }
}

void fun( int x = 1, int p = 0, long long v = 0 )
{
    if ( p )
    {
        if ( !id || v + tab[ x ] > maks || v + tab[ x ] == maks && x < id )
        {
            maks = v + tab[ x ];
            id = x;
        }
    }
    for ( int i = 0; i < G[ x ].size(); ++i )
    {
        if ( G[ x ][ i ] != p )
        {
            fun( G[ x ][ i ], x, v - D[ x ][ i ] );
        }
    }
}

int main()
{
    int n, q, x, y, xd = 1;
    long long z;

    scanf( "%d%d", &n, &q );

    for ( int i = 1; i <= n; ++i ) scanf( "%d", &tab[ i ] );

    for ( int i = 1; i < n; ++i )
    {
        scanf( "%d%d%lld", &x, &y, &z );
        change( x, y, z );
        change( y, x, z );
    }

    while ( q-- )
    {
        scanf( "%d", &x );
        id = 0;

        if ( x == 1 )
        {
            scanf( "%d%d", &x, &y );
            tab[ x ] = y;
        }
        else
        {
            scanf( "%d%d%lld", &x, &y, &z );
            change( x, y, z );
            change( y, x, z );
        }
        fun( xd );
        xd = id;
        printf( "%d ", xd );
    }
}