知道黑暗城堡有 N 個房間，M 條可以制造的雙向通道，以及每條通道的長度。
城堡是樹形的并且滿足下面的條件：
設(shè) Di為如果所有的通道都被修建，第 i 號房間與第 1 號房間的最短路徑長度；
而 Si 為實際修建的樹形城堡中第 i 號房間與第 1號房間的路徑長度；
要求對于所有整數(shù) i(1≤i≤N)，有 Si=Di成立。
你想知道有多少種不同的城堡修建方案。當然，你只需要輸出答案對 231?1 取模之后的結(jié)果就行了。

第一行為兩個由空格隔開的整數(shù) N,M;
第二行到第 M+1 行為3 個由空格隔開的整數(shù) x,y,l：表示 x 號房間與 y 號房間之間的通道長度為 l。

一個整數(shù)：不同的城堡修建方案數(shù)對 2³¹?1 取模之后的結(jié)果。

樣例說明
一共有 4 個房間，6 條道路，其中 1 號和 2 號，1 號和 3 號，1 號和 4 號，2 號和 3 號，2 號和 4 號，3 號和 4 號房間之間的通道長度分別為 1，2，3，1，2，1。
而不同的城堡修建方案數(shù)對 231?1 取模之后的結(jié)果為 6。
數(shù)據(jù)范圍:
對于全部數(shù)據(jù)，1≤N≤1000，1≤M≤N(N?1)/2,1≤l≤200。

信息學一本通 圖論