Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3902
Triangle

Time Limit: 15 Seconds      Memory Limit: 65536 KB

There are many anime that are about "love triangles": Alice loves Bob, and Charlie loves Bob as well, but Alice hates Charlie. You are thinking about an anime which has n characters. The characters are labeled from 1 to n. Every pair of two characters can either mutually love each other or mutually hate each other (there is no neutral state).

You hate bad triangles (A-B are in love but B-C hate each other and A-C hate each other), and you also hate it when nobody is in love. So, considering any three characters, you will be happy if exactly two pair is in love (A and B hate each other, and C loves both A and B), or if all three pairs are in love (A loves B, B loves C, C loves A).

You are given a list of m known relationships in the anime. You know for sure that certain pairs love each other, and certain pairs hate each other. You're wondering how many triangles can make you happy while you can fill in the remaining relationships. Two triangles are considered the same if two triangles have the same characters and the relationships between them are the same. Print this count modulo 999983.

Input

The input file contains multiple test cases.

The first line contains two integers n,m(1≤ n ≤ 100000, 0≤ m ≤ 100000), indicating the number of characters and the number of known relationships between them.

The following m lines contains three integers x,y,z(1≤ x,y ≤ n, 0≤z≤ 1) indicating the relationships between x and y, if z = 0, x hates y. If z = 1, x loves y.

Output

For each test case, output one single number equal to the number of triangles makes you happy. The answer should modulo 999983

Sample Input

3 3
1 2 1
1 3 1
2 3 1
4 2
1 2 1
3 4 0

Sample Output

1
8

Author: GAN, Tiansheng
Source: ZOJ Monthly, September 2015
Submit    Status