题目背景

「爱人不及，仇敌不必，伴着回忆，隐于朝夕」

“emo了？”

「没有没有」

“你怎么像受了什么情伤…”

「阿巴阿巴」

题目描述

神经系统可以看作一张有 $n$ 个节点的无向图，有边权，节点之间的连边情况决定了鸽子的心情。

一个连通分量如果包含恰好一个简单环，其对心情的贡献为环上边权之和，否则其对心情的贡献为 $0$。鸽子的心情是每个连通分量对心情的贡献之和。

已知图上至多有 $m$ 条边。情绪是短暂的、不稳定的，这些边可能出现也可能不出现，因此可能的生成子图共有 $2^m$ 种。你需要求出所有生成子图中鸽子的心情之和，对 $1914270647$ 取模。

考虑到心情的复杂性，你只需处理规模很小的图。

输入格式

第一行两个正整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示节点 $u,v$ 之间有边权为 $w$ 的边。

输出格式

一个整数，表示答案。

样例一

input

2 1
1 2 1

output

0

样例二

input

4 5
1 2 100000
2 3 1000000
3 4 10000000
4 1 100000000
1 3 1000000000

output

701588059

样例三

input

14 27
1 6 1
5 10 1
3 6 1
3 5 1
10 1 1
6 5 1
5 1 1
3 10 1
11 2 1
8 4 1
4 14 1
9 12 1
12 13 1
11 9 1
13 8 1
4 9 1
13 2 1
4 13 1
8 14 1
9 8 1
2 8 1
14 12 1
9 14 1
2 14 1
2 4 1
4 11 1
11 13 1

output

222304512

样例四

见下发文件中的 $\text{ex_emotion4.in/ans}$。

限制与约定

所有数据满足 $2\le n \le 21$，$1\le m\le \frac {n(n-1)}2$，$1\le u,v\le n$，$0\le w< 1914270647$。输入的图没有重边、自环。