Problem:

決まりごとの多いジム

　

イヅア村のスポーツジムには$1$から$N$までの番号が付いた$N$台のトレーニング機器があります。トレーニング機器を１回利用するには、その機器の番号が書かれたチケットが１枚必要です。トレーニング機器を１回利用したときの消費カロリーは、機器ごとに決まっています。

このスポーツジムのチケットを何枚かもらったアツシ君は、運動不足解消のためにジムに行きました。このジムでは、利用者が運動をやりすぎて体を痛めないように、機器の利用回数にルールがあります。たとえば、「２番の機器は３番の機器よりも５回以上多く使ってはいけません」というようなルールです。機器を使う人は、ルールを守って機器を利用しなければなりません。

アツシ君は、もらったチケットを使って、ルールで許される範囲でなるべく多くのカロリーを消費したいと思っています。

もらったチケットとそれぞれの機器の情報が与えられたとき、ルールを守ったときの消費カロリーの最大値を求めるプログラムを作成しなさい。

入力

入力は以下の形式で与えられる。

$N$ $R$
$t_1$ $e_1$
$t_2$ $e_2$
:
$t_N$ $e_N$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
:
$a_R$ $b_R$ $c_R$

１行目にトレーニング機器の台数$N$ ($1 \leq N \leq 100,000$)とルールの数$R$ ($0 \leq R \leq 100,000$)が与えられる。続く$N$行に、$i$番の機器について、アツシ君がもらったチケットの枚数$t_i$ ($1 \leq t_i \leq 200,000$)とその機器を使ったときの消費カロリー$e_i$ ($0 \leq e_i \leq 100,000$)が与えられる。続く$R$行に、「$a_i$番の機器は$b_i$番の機器よりも$c_i$回以上多く使ってはいけません」というルールを表す数$a_i$ ($1 \leq a_i \leq N$)、$b_i$ ($1 \leq b_i \leq N$)、$c_i$ ($1 \leq c_i \leq 100,000$)が与えられる。

入力は以下の制約を満たす。

	同じ機器のペアに対するルールは１度しか与えられない($i \ne j$なら$a_i \ne a_j$または$b_i \ne b_j$)。

	同じ機器自身に対するルールは与えられない($a_i \ne b_i$)。

出力

  消費カロリーの最大値を１行に出力する。

入出力例

入力例１

3 2
5 1
10 4
6 2
2 1 3
3 2 1

出力例１

45

もらったチケットを使って、ルールを守って使える各機器の最大の回数は、$1$番が$5$回、$2$番が$7$回、$3$番が$6$回なので、消費カロリーの最大値は$5 \times 1 + 7 \times 4 + 6 \times 2  = 45$となる。

入力例２

4 5
5 1
6 2
2 3
7 1
1 2 4
2 1 3
1 3 2
3 2 3
3 4 2

出力例２

26

入力例３

1 0
200000 100000

出力例３

20000000000



Sample input:
3 2
5 1
10 4
6 2
2 1 3
3 2 1


Sample output:
45

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


class Edge:
    def __init__(self,arg_to,arg_cost):
        self.to = arg_to
        self.cost = arg_cost

class Info:
    def __init__(self,arg_node_id,arg_sum_cost):
        self.node_id = arg_node_id
        self.sum_cost = arg_sum_cost

    def __lt__(self,another):
        return self.sum_cost < another.sum_cost


N,R = map(int,input().split())

G = [[] for _ in range(N+1)]
value = [None]*(N+1)
root = 0

for i in range(1,N+1):
    cost,tmp = map(int,input().split())
    G[root].append(Edge(i,cost))
    value[i] = tmp

for _ in range(R):
    to_,from_,cost = map(int,input().split())
    G[from_].append(Edge(to_,cost-1))

min_cost = [BIG_NUM]*(N+1)
min_cost[root] = 0;
Q = []

heappush(Q, Info(root,0))

while len(Q) > 0:
    info = heappop(Q)
    if info.sum_cost > min_cost[info.node_id]:
        continue
    for edge in G[info.node_id]:
        if min_cost[edge.to] > info.sum_cost+edge.cost:
            min_cost[edge.to] = info.sum_cost+edge.cost
            heappush(Q, Info(edge.to,min_cost[edge.to]))

ans = 0
for i in range(1,N+1):
    ans += min_cost[i]*value[i]

print("%d"%(ans))