本题s[i]为实际树上i节点到1节点的距离,
d[i]为全树上i节点到1节点的最小距离
s[i] = d[i]，显然s是最小生成树
而求d跑一遍dijkstra即可
跑分195ms 很快

//acwing 349
//dijkstra 最小生成树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define INF 2147483647
using namespace std;

const int N = 1010;
typedef long long LL;
typedef pair<int, int> PII;

struct Edge{
    int nxt,to,v;
}edge[N * (N - 1)];


int n,m,cnt;
int h[N];
int dist[N], vis[N];
LL res[N];

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)){if (ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;
}

inline void AddEdge(int a, int b, int c){
    edge[++cnt].nxt = h[a];
    edge[cnt].to = b;
    edge[cnt].v = c;
    h[a] = cnt;
}

void dijkstra(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while(!heap.empty()){
        int u = heap.top().second;
        heap.pop();

        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = h[u]; i; i = edge[i].nxt){
            int v = edge[i].to;
            if (dist[v] > dist[u] + edge[i].v){
                dist[v] = dist[u] + edge[i].v;
                heap.push({dist[v], v});
            }
        }
    }
}

signed main(signed argc, char** argv){
    //ios ;
    cin >> n >> m;
    register int a,b,c;
    for (int i = 1; i <= m; i ++) {
        a = read(),b = read(),c = read();
        AddEdge(a, b, c), AddEdge(b, a, c);
    }

    dijkstra();

    LL ans = 1;
    for (int i = 1; i <= n; i ++){
        for (int j = h[i]; j ; j = edge[j].nxt){
            int v = edge[j].to, w = edge[j].v;
            if (dist[v] == dist[i] + w) res[v] ++;
        }
    }

    for (int i = 1; i <= n; i ++) 
    if (res[i]) ans = ans * res[i] % INF;

    cout << ans << endl;
    return 0;
}