#include <bits/stdc++.h>
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
using namespace std;
long long used[101][101];
struct edge {
  long long to, cost;
};
struct dijkstra {
  using P = pair<long long, long long>;
  priority_queue<P, vector<P>, greater<P>> q;
  vector<vector<edge>> ed;
  vector<long long> dist;
  long long sz;
  dijkstra(long long size) {
    sz = size;
    ed.resize(size);
  }
  void reset() {
    dist.assign(sz, -1);
    q = priority_queue<P, vector<P>, greater<P>>();
  }
  void ae(long long from, long long to, long long cost) {
    ed[from].push_back({to, cost});
  }
  long long cal(long long start, long long end) {
    reset();
    q.push({0, start * 1001});
    while (!q.empty()) {
      P tp = q.top();
      q.pop();
      long long from = tp.second % 1000;
      tp.second /= 1000;
      if (dist[tp.second] != -1) continue;
      dist[tp.second] = tp.first;
      if (dist[tp.second] > tp.first) {
        used[from][tp.second] = 1;
        used[tp.second][from] = 1;
      }
      for (auto nn : ed[tp.second]) {
        if (dist[nn.to] != -1) continue;
        q.push({nn.cost + tp.first, nn.to * 1000 + tp.second});
      }
    }
    return dist[end];
  }
  long long getd(long long end) { return dist[end]; }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  vector<long long> a(m), b(m), c(m);
  for (long long i = 0; i < (long long)(m); i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
    used[a[i]][b[i]] = 2;
    used[b[i]][a[i]] = 2;
  }
  dijkstra dj(n);
  for (long long j = 0; j < (long long)(m); j++) {
    dj.ae(a[j], b[j], c[j]);
    dj.ae(b[j], a[j], c[j]);
  }
  for (long long i = 0; i < (long long)(n); i++) {
    dj.cal(i, n - 1);
  }
  long long cnt = 0;
  for (long long i = 0; i < (long long)(101); i++)
    for (long long j = long long(i + 1); j < long long(101); j++)
      if (used[i][j] == 2) {
        cnt++;
      }
  cout << cnt << endl;
  return 0;
}
