牛牛当上了牛客国的国王，在牛客国一共有个城市，这个城市之间原有条航路，但是由于城市航路规划，需要删除一些航路，使剩下的航路刚好能让这个城市联通，并且剩下的航路总载客量最大。牛客国的计数方式比较特别，他们喜欢用组合数来计数。所以两个城市之间航路的载客量也是用表示的。作为国师你能告诉牛牛剩下的航路的总载客量是多少呢，由于数可能很大请对取模后告诉牛牛。

输入描述:

第一行为两个整数和，表示城市数量和原有航路条数。接下来有行，每行有四个整数，表示一条航路之间的两个城市编号和航路载客量中的和。

输出描述:

输出为一行，输出剩下的航路的总载客量并对取模，若剩下的航路不能让所有城市联通输出。