AC

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

typedef long long ll; typedef pair<int, int> pii;

const int MAXN = 1005; const int MOD = (1LL << 31) - 1; // 2^31 - 1

int N, M; vector g[MAXN]; int dist[MAXN]; bool vis[MAXN];

void dijkstra(int start) {

memset(dist, 0x3f, sizeof(dist));
memset(vis, 0, sizeof(vis));
dist[start] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, start});
while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (auto &e : g[u]) {
        int v = e.first, w = e.second;
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

}

int main() {

ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> N >> M;
for (int i = 0; i < M; i++) {
    int x, y, l;
    cin >> x >> y >> l;
    g[x].push_back({y, l});
    g[y].push_back({x, l});
}

dijkstra(1);

vector<int> cnt(N + 1, 0);
// 对每个点 i，找可能的父亲 u (u != i)
for (int i = 1; i <= N; i++) {
    for (auto &e : g[i]) {
        int j = e.first, w = e.second;
        if (dist[i] + w == dist[j]) {
            cnt[j]++;
        }
    }
}

ll ans = 1;
for (int i = 2; i <= N; i++) {
    ans = (ans * cnt[i]) % MOD;
}
cout << ans << "\n";

return 0;

}