You are given a directed weighted graph with n nodes and 2n - 2 edges. The nodes are labeled from 1 to n, while the edges are labeled from 1 to 2n - 2. The graph's edges can be split into two parts. You are given q queries. There are two types of queries Given these queries, print the shortest path lengths. The first line of input will contain two integers n, q (2 ≤ n, q ≤ 200 000), the number of nodes, and the number of queries, respectively. The next 2n - 2 integers will contain 3 integers ai, bi, ci, denoting a directed edge from node ai to node bi with weight ci. The first n - 1 of these lines will describe a rooted spanning tree pointing away from node 1, while the last n - 1 of these lines will have bi = 1. More specifically, The next q lines will contain 3 integers, describing a query in the format described in the statement. All edge weights will be between 1 and 106. For each type 2 query, print the length of the shortest path in its own line.