// P10929 黑暗城堡
#include <bits/stdc++.h>
#define LL long long
#define MAXN 1002
using namespace std;

const LL MOD = (LL)(1<<31)-1;
int n, m, dis[MAXN], e[MAXN][MAXN];
bool vis[MAXN];

LL dijkstra() {
    LL ans = 1;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == -1 || dis[u] > dis[j]))
                u = j;
        vis[u] = true;
        for (int j = 1; j <= n; j++)
            if (dis[j] > dis[u] + e[u][j])
                dis[j] = dis[u] + e[u][j];
    }

    for (int i = 2; i <= n; i++) {
        int s = 0;
        for (int j = 1; j <= n; j++)
            if (dis[i] == dis[j] + e[i][j])
                s++;
        if (s > 0)
            ans = (LL)ans * s % MOD;
    }

    return ans;
}

int main() {
    memset(e, 0x3f, sizeof(e));
    cin >> n >> m;
    int u, v, w;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        e[u][v] = e[v][u] = min(e[v][u], w);
    }
    printf("%lld", dijkstra());

    return 0;
}