3174. 激突冲击

【题目描述】

布基纳法索空军最近在瓦加杜古上空18000米处发现了一艘残破的航天母舰，在经过精细的搜查之后，布基纳法索空军发现这架空母上的大多数武器装置仍处于工作状态！如果让其启动，那么整个国家甚至周边地区都有可能遭受灭顶之灾！所幸整架空母之上的唯一一位幸存者——一位自称HS的神奇生物在见到布基纳法索空军之后告诉空军们关闭武器系统的方式——把船拆了。可是由于HS的身体构造过于神奇，被布基纳法索国家医院征用去做活体解剖了，空军战士们只能自行拆船。

研究发现，空母由$N$个子舱室和$M$个活塞组成，只要按照正确的方式推动活塞，舱室就会自动解体。但是要推动活塞需要在活塞相连的两个舱室分别施加一定的力（别问我为什么不能只推一个）并且两个力之间有一定约束关系。综上，布基纳法索空军决定在每个舱室上放一定量的炸药，用冲击力推动活塞。

下面给出舱室间推力关系$(T,A,B)$：

$T=1$代表A舱与B舱推力相等；

$T=2$代表A舱推力小于B舱；

$T=3$代表A舱推力不小于B舱；

$T=4$代表A舱推力大于B舱；

$T=5$代表A舱推力不大于B舱。

由于炸药用量和所产生推力成正比，因此上述关系可视为在各舱室放置炸药数量的关系。

为了尽可能的减少炸药的用量，你需要求出整个爆破过程炸药的消耗总量（其中最少的舱室放置1单位的炸药，各舱室炸药量为整单位）,如果不可能完成任务，输出-1。

【输入格式】

第一行两个正整数$N,M(N,M\leq 10^5)$。

下面$M$行，每行描述一组$(T,A,B)$关系

【输出格式】

整个爆破过程炸药的消耗总量，如果不可能完成任务，输出-1。

【样例输入】

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

【样例输出】

11

【来源】

改编自SCOI2011