问题 25876 --银河

25876: 银河

时间限制: 3 Sec  内存限制: 128 MB
提交: 108  解决: 22
[提交][状态][讨论版][数据上传:][下载FPS3元][下载测试数据3元][5096kb]

题目描述

银河中的恒星浩如烟海,但是我们只关注那些最亮的恒星。我们用一个正整数来表示恒星的亮度,数值越大则恒星就越亮,恒星的亮度最暗是1。现在对于N 颗我们关注的恒星,有M 对亮度之间的相对关系已经判明。你的任务就是求出这N 颗恒星的亮度值总和至少有多大。

数据范围与约定
对于30% 的数据,N≤100。
对于 100% 的数据,N≤100 000,M≤100 000。

输入

第一行给出两个整数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 的亮度。

输出

输出一个整数表示答案。

样例输入

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

样例输出

11

提示


数据范围与约定



对于30% 的数据,N≤100。



对于
100% 的数据,N≤100 000,M≤100 000。

来源

[提交][状态]