DongDong的生成树
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

DongDong和萨摩耶一起在玩拼图,然而萨摩耶很粗心,把拼图都搞丢了,现在萨摩耶找到了一些丢失的拼图,并且想查询当前的最小生成树是多大。给定n个点,m次操作,F x y z操作表示将x,y之间连一条边权为z的边,Q表示·查询当前的最小生成树为多大(若此时图没有联通,输出-1

输入描述:

第一行两个整数,n,m

接下来m行,F x y z操作表示将x,y之间连一条边权为z的边,Q表示·查询当前的最小生成树为多大(若此时图没有联通,输出-1)

数据范围:n<=10000,m<=100000对于边的w,w<=1000000

输出描述:

对于每一次询问输出当前的最小生成树,若没有则输出-1
示例1

输入

复制
5 8
F 1 2 1
F 3 2 3
Q
F 1 4 100
F 2 5 50
Q
F 1 5 1
Q

输出

复制
-1
154
105