#include<bits/stdc++.h> using namespace std; const int max_n = 105,Mod = 1e9; int n,m,u,v,w,dis[max_n][max_n],grahy[max_n][max_n],ans; int floyd(int l,int r){ int k = r; for(int i = l; i <= r; i ++) dis[i][k] = grahy[i][k], dis[k][i] = grahy[k][i]; for(int i = l; i <= r; i ++) for(int j = l; j <= r; j ++) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); dis[k][j] = min(dis[k][j], dis[k][i] + dis[i][j]); dis[i][k] = min(dis[i][k], dis[i][j] + dis[j][k]); } for(int i = l; i <= r; i ++) for(int j = l; j <= r; j ++) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); dis[k][j] = min(dis[k][j], dis[k][i] + dis[i][j]); dis[i][k] = min(dis[i][k], dis[i][j] + dis[j][k]); } int res = 0; for(int i = l; i <= r; i ++) for(int j = i; j <= r; j ++) { res = (res + dis[i][j]) % Mod; } return res; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) grahy[i][j] = 1e9; for(int i = 1; i <= n; i ++) grahy[i][i] = 0; for(int i = 1; i <= m; i ++) { int u, v, w; cin >> u >> v >> w; grahy[u][v] = min(grahy[u][v], w); grahy[v][u] = min(grahy[v][u], w); } int ans = 0; for(int i = 1; i <= n; i ++) { for(int u = 1; u <= n; u ++) for(int v = 1; v <= n; v ++) dis[u][v] = 1e9; for(int u = 1; u <= n; u ++) dis[u][u] = 0; for(int j = i; j <= n; j ++) ans = (ans + floyd(i, j)) % Mod; } cout << ans << '\n'; return 0; }