U188981 赛车

无咕_最近迷上赛车游戏啦！所以这道题跟赛车没有任何关系（

游戏出了一个新的模式： 地图有 $n$ 个赛段点（包括起点），由 $n-1$ 条道路（因为游戏设计的很银杏，所以道路是双向的）连接。两个赛段之间一定有且仅有一条道路，每条道路都有自己的长度 $q_i$（表示玩家需要花费 $q_i$ 的时间才可以走过）。每个赛段点可能会在某个时间之后有积分宝箱（时间是给出的），玩家到该赛段点时可以获得该点所有的全部积分（一个点可以有多个积分宝箱）。 游戏开始时，系统依次会给出玩家 $m$ 条指令（如果该指令属于“任务”，那么玩家必须完成“任务”才会给出下一条指令）。指令内容包括： - （任务）给出 $l,r$，表示玩家需要从 $l$ 点走到 $r$ 点。如果玩家当前不在 $l$ 点，需要自行移动到 $l$ 点（必须是从 $l$ 点到 $r$ 点才行，方向固定。并且路线一定唯一）。 - 给出 $x,w$，表示在第 $x$ 个赛段点上出现了一个积分数量为 $w$ 的宝箱（认为该操作是瞬间完成的）。$w$ 可能为负数。注意，如果放玩家正好处在积分宝箱的位置，那么该积分宝箱直接被获得。 无咕_是高玩，所以不会出现任何失误导致（如果事实是这样就好了）。无咕_是菜鸡，所以他找到了你并请你求出他所需走的路程，并承诺将他获得的积分给你一半（向下取整）。

第一行两个整数 $n,m$，表示赛段点的总数和指令总数。 第二行到第 $n$ 行，每行两个整数 $u,v$ 和一个实数 $w$，表示有条从 $u$ 到 $v$ 的路线，玩家需要花 $w$ 秒才能走过。 接下来 $m$ 行，每行先给出 $op$。 如果 $op=1$，那么后面跟着两个整数 $l,r$，表示指令 $1$； 如果 $op=2$，那么后面跟着两个整数 $x,w$，表示指令 $2$。

第一行输出无咕_所需走的路程。 第二行输出你能获得的报酬。

注意！~~出题人不想卡你，但也不想让你好过~~保证给出的道路长度能被存储。 对于 $100\%$ 的数据，$n,m\le 10^5,-10^4\le w_i\le 10^4,0\le q_i\le 10^4,$