Component weight
Problem
Edges are added to an undirected weighted graph. Write a program that at some point finds the sum of the weights of edges in a connected component.
Input
The first line contains two numbers n and m (1 <= n, m <= 106) - the number of vertices in the column and the number of additions and requests made. This is followed by m lines describing the addition or request. Each line consists of two or four numbers. The first of the numbers indicates the operation code. If the first number is 1, then it is followed by three more numbers x, y, w. This means that an edge is added to the graph from vertex x to vertex y of weight w. (1 <= x < y <= n, 1 <= w <= 103). Multiple edges are allowed. If the first number is 2, then exactly one number x follows it. This means that it is necessary to answer the question, what is the sum of edges in the connected component to which the vertex x (1 <= x <= n) belongs.
Output
For each operation with code
2 print the answer to the given problem. Print the answer to each request on a separate line.
Examples
| # |
Input |
Output |
| 1 |
6 10
2 1
1 1 2 1
2 1
1 2 4 2
2 1
1 1 4 3
2 1
1 3 5 3
2 5
2 6
|
0
1
3
6
3
0
|