#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

int CityCount;
int ChangesCount;

struct rInfo{
    int ToCity;
    long long Cost;
    bool operator<(const rInfo& a)const;
};

    bool rInfo::operator<(const rInfo& a)const{
        return ToCity < a.ToCity;
    }

class City{
    private :
        long long Banan;
        long long Profit;
        long long Rute;
        int Number;
        int Iter;
        int InQueue;
        int Visited;
        vector<rInfo> Connect;
    public :
        City( int aNumber, long long aBanan);
        void AddConnect(int aCity, long long aCost);
        void AddToQueue(vector<int>& aQueue, int aIter);
        int BinarySearch(int aCity);
        void NewBanan(long long aBanan);
        void NewCost(int aCity, long long aNewCost);
        void NewStart(int aIter);
        void QueueIter(int aIter);
        void Print();
        void PrintRoad();
        bool SortCmp(const rInfo &a, const rInfo &b);
        void SortRoad();
        void TestProfit();
};


vector< City >  CityList;
vector< int >  Queue;

int Curent;
int Best;
//long long BestCost;

const long long Minimum=-9223372036854775807;
const long long Maximum= 9223372036854775807;

City::City(int aNumber, long long aBanan){
    Banan   = aBanan;
    Number  = aNumber;
    Profit = Minimum;
    Rute = 0;
    Iter = -1;
    InQueue = -1;
    Visited = -1;
    Connect.reserve(32);
}

void City::AddConnect(int aCity, long long aCost){
    rInfo oInfo;
    oInfo.ToCity=aCity;
    oInfo.Cost=aCost;
    Connect.push_back(oInfo);
}

void City::AddToQueue(vector<int>& aQueue, int aIter){
    for(auto it:Connect){
        if(CityList[it.ToCity].Iter<aIter){
            Queue.push_back(it.ToCity);
            CityList[it.ToCity].Rute = it.Cost+Rute;
            CityList[it.ToCity].Iter = aIter;
            CityList[it.ToCity].InQueue = aIter;
        }else{
            if(CityList[it.ToCity].Rute>Rute+it.Cost){
                CityList[it.ToCity].Rute=Rute+it.Cost;
                if(CityList[it.ToCity].InQueue!=aIter){
                    Queue.push_back(it.ToCity);
                    CityList[it.ToCity].InQueue = aIter;
                }
            }
        }
    }
}

int City::BinarySearch(int aCity){
   int first=0;
   int last=Connect.size();
   while (first <= last) {
       int mid = (first + last) / 2;  // compute mid point.
       if (aCity > Connect[mid].ToCity)
           first = mid + 1;  // repeat search in top half.
       else if (aCity < Connect[mid].ToCity)
           last = mid - 1; // repeat search in bottom half.
       else
           return mid;     // found it. return position /////
   }
   return -(first + 1);    // failed to find key
}

void City::NewBanan(long long aBanan){
    Banan = aBanan;
}

void City::NewCost(int aCity, long long aNewCost){
    Connect[BinarySearch(aCity)].Cost = aNewCost;
}

void City::NewStart(int aIter){
    InQueue=aIter;
    Iter=aIter;
    Rute=0;
    Profit=Minimum;
}

void City::Print(){
    cout << "Miasto nr:" <<Number << endl;
    cout << "Banany po:" <<Banan  << endl;
    cout << "Koszt dro:" <<Rute   << endl;
    cout << "Zysk     :" <<Banan-Rute<<endl;
    cout << "Profit   :" <<Profit << endl;
    for(auto it:Connect){
        cout << "Droga do:" << it.ToCity << "  Koszt :"<<it.Cost << endl;
    }
    cout << endl;
}

void City::PrintRoad(){
    cout << "Miasto nr:" <<Number <<" Polaczone z:";
    for(int oLoop=0;oLoop<Connect.size();oLoop++){
        cout << Connect[oLoop].ToCity<<" ";
    }
}

void City::QueueIter(int aIter){
    InQueue=aIter;
}

void City::SortRoad(){
    sort(Connect.begin(),Connect.end());
};

void City::TestProfit(){
    Profit = Banan - Rute;
    if(Profit>CityList[Best].Profit){
        Best=Number;
    }else{
        if((Profit==CityList[Best].Profit)&&(Number<Best))Best=Number;
    }
}

//----------------------------------------------------------------------//


void CalculateCost(int aIter){
    Curent = Best;
    Best=0;
    CityList[Curent].NewStart(aIter);
    CityList[Curent].AddToQueue(Queue,aIter);
    int oCurent;
    while (!Queue.empty()){
        oCurent = Queue.back();
        Queue.pop_back();
        CityList[oCurent].AddToQueue(Queue,aIter);
        CityList[oCurent].QueueIter(-1);
        CityList[oCurent].TestProfit();
    };
    cout << Best << " ";
}

void InitCity(int aCityCount){
    CityList.reserve(aCityCount);
    CityList.push_back(City(0,0));
    Queue.reserve(aCityCount);
    for(int oLoop=1;oLoop<aCityCount;oLoop++){
        long long oBanan;
        cin >> oBanan;
        CityList.push_back(City(oLoop, oBanan));
    }
}

void InitConnect(int aConnectCount){
    int oCityA;
    int oCityB;
    long long oCost;
    for(int oLoop=1;oLoop<aConnectCount;oLoop++){
        cin >> oCityA >> oCityB >> oCost;
        CityList[oCityA].AddConnect(oCityB, oCost);
        CityList[oCityB].AddConnect(oCityA, oCost);
    }
    for(auto it:CityList){
        it.SortRoad();
    }
    Curent=1;
}

void PrintCity(){
    for(auto it:CityList){
        it.Print();
    }
}
void ReadData(){
    cin >> CityCount >> ChangesCount;
    InitCity   ( CityCount + 1);
    InitConnect( CityCount    );
}

void Analize(){
    Best = 1;
    int oCityA;
    int oCityB;
    int oValue;
    long long oNewCost;
    long long oNewBanan;
    for(int oLoop=0;oLoop<ChangesCount;oLoop++){
        cin >> oValue;
        if(oValue==1){
            cin >> oCityA >> oNewBanan;
            CityList[oCityA].NewBanan(oNewBanan);
        }else{
            cin >> oCityA >> oCityB >> oNewCost;
            CityList[oCityA].NewCost(oCityB, oNewCost);
            CityList[oCityB].NewCost(oCityA, oNewCost);
        };
        CalculateCost(oLoop);
    }
}

int main()
{
    ReadData();
    Analize();
    return 0;
}