#include using namespace std; int mod = 1000000007; int main() { int N,M,K; cin >> N >> M >> K; vector>> road(N); for(int i = 0; i < M; i++) { int X,Y,Z; cin >> X >> Y >> Z; X--; Y--; road[X].push_back({Y,Z}); road[Y].push_back({X,Z}); } vector> dist(N,vector(2,-mod)); long long tmp = 1,tmp2 = 1; bool flag = true; for(int i = 0; i < N; i++) { if(dist[i][0] == -mod && dist[i][1] == -mod) { if(road[i].size() == 0) { tmp *= K; tmp2 *= K-1; tmp %= mod; tmp2 %= mod; } dist[i][0] = 0; vector dist2; queue> que; que.push({i,0}); while (!que.empty()) { pair x = que.front(); que.pop(); dist2.push_back(x.first); for(int j = 0; j < road[x.first].size(); j++) { pair nx = {road[x.first][j].first,x.second^1}; if(dist[nx.first][nx.second] == -mod) { dist[nx.first][nx.second] = road[x.first][j].second-dist[x.first][x.second]; que.push(nx); } else if(dist[nx.first][nx.second] != road[x.first][j].second-dist[x.first][x.second]){ flag = false; } } } int gmi = mod,gmx = -mod,kmi = mod,kmx = -mod; int res = -mod; for(int j = 0; j < dist2.size(); j++) { if(dist[dist2[j]][0] != -mod) { gmi = min(gmi,dist[dist2[j]][0]); gmx = max(gmx,dist[dist2[j]][0]); } if(dist[dist2[j]][1] != -mod) { kmi = min(kmi,dist[dist2[j]][1]); kmx = max(kmx,dist[dist2[j]][1]); } if(dist[dist2[j]][0] != -mod && dist[dist2[j]][1] != -mod) { int a = abs(dist[dist2[j]][0]-dist[dist2[j]][1]); if(a%2 == 1) { flag = false; } if(res == -mod) { res = a/2; } else if(res != a/2) { flag = false; } } } if(res != -mod) { if(res >= 1 && res <= K && gmi+res >= 1 && gmx+res <= K && kmi-res >= 1 && kmx-res <= K) { if(gmx+res == K || kmx-res == K) { tmp2 = 0; } } else { flag = false; } } else { int mi = 0,mx = 0; mi = max(1,1-gmi); mx = min(K,K-gmx); mi = max(mi,kmx-K); mx = min(mx,kmi-1); if(mi > mx) { flag = false; } tmp *= mx-mi+1; tmp %= mod; tmp2 *= mx-mi; tmp2 %= mod; } } } if(!flag) { cout << 0 << endl; return 0; } cout << (tmp+mod-tmp2)%mod << endl; }