#Pscc14. 【例题4】恒星的亮度

    ID: 600 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>强连通分量赛制:OI来源:wyfoj http://127.0.0.1

【例题4】恒星的亮度

【例题4】恒星的亮度

题目描述

银河中的恒星浩如烟海,但是我们只关注那些最亮的恒星。

我们用一个正整数来表示恒星的亮度,数值越大则恒星就越亮,恒星的亮度最暗是1。

现在对于N颗我们关注的恒星,有M对亮度之间的相对关系已经判明。

你的任务就是求出这N颗恒星的亮度值总和至少有多大。

输入格式

第一行给出两个整数N和M。

之后M行,每行三个整数T,A,B,表示一对恒星(A,B)之间的亮度关系。恒星的编号从1开始。

如果T=1,说明A和B亮度相等。

如果T=2,说明A的亮度小于B的亮度。

如果T=3,说明A的亮度不小于B的亮度。

如果T=4,说明A的亮度大于B的亮度。

如果T=5,说明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

提示

对于100%的数据,1<=N<=105,1<=M<=1051<=N<=10^5,1<=M<=10^5。