TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8253
  • 题目
  • P8253数字游戏2
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2s 256MB
    问题描述

    有一个由$n$个整数组成的序列$a$,其中的元素为 \(a_{1}, a_{2},..., a_{n}\)。起初你只知道 \(a_{1}\) 的值,但是有$m$个提示信息。每个提示信息包含3个数$x, y, z$,表示 \(a_{x} - a_{y}\) 的值为 \(z\) 。所有提示信息的$x$和$y$都是可见的,而获取第$i$条提示信息的$z$则需要花费 \(b_{i}\) 的代价。问你是否可以知道序列$a$中所有元素的值,如果可以,那么知道序列$a$中所有元素的值最少需要花费的总代价是多少。

    输入格式

    第一行包含一个整数$T \left ( 1 \leqslant T \leqslant 100 \right )$,表示数据组数。

    接下来有$T$组数据。每组数据的第一行包含两个整数 \(n, m \left ( 1 \leqslant n \leqslant 10^{5}, 0 \leqslant m \leqslant 2 \times 10^{5} \right )\) ;之后有$m$行,每行包含3个整数,其中第$i$行为 \(x_{i}, y_{i}, b_{i} \left ( 1 \leqslant x_{i} < y_{i} \leqslant n, 1 \leqslant b_{i} \leqslant 10^{4} \right )\),代表第$i$条提示信息。

    保证所有数据中$m$的和不超过$2 \times 10^{5}$。

    输出格式

    对于每组数据输出一行,包含一个整数,表示你知道序列$a$中所有元素的值最少需要花费的总代价,若你不能知道序列$a$中所有元素的值,则输出-1。

    样例输入

    2
    2 2
    1 2 1
    1 2 3
    3 3
    1 2 1
    1 3 2
    2 3 3

    样例输出

    1
    3

    提示

    对于样例中的第二组测试数据,可以先花费1的代价查看第1条提示信息的$z$,从而推导出$a_{2}$的值;再花费2的代价查看第2条提示信息的$z$,从而推导出$a_{3}$的值。因此最少需要花费3的总代价,知道了序列$a$中所有元素的值。