UPGRADE

#include <bits/stdc++.h>
#define int64_t long long
using namespace std;

const int N = 1e5 + 5;
const int oo = 1000111000;
typedef pair<int64_t, int> ii;

int n, m;
vector<ii> graph[N];
int64_t d[N];
vector<int> pre[N];

void dijkstra() {
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    fill(d + 1, d + n + 1, oo);
    d[1] = 0;
    pq.push(ii(0, 1));

    while(pq.size()) {
        int u = pq.top().second;
        int du = pq.top().first;
        pq.pop();

        if(du != d[u]) continue;

        for(int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].second;
            int uv = graph[u][i].first;

            if(d[v] > du + uv) {
                d[v] = du + uv;
                pre[v].clear();
                pre[v].push_back(u);
                pq.push(ii(d[v], v));
            }
            else if(d[v] == du + uv) {
                pre[v].push_back(u);
            }
        }
    }
}

vector<int> a[N];
void build(int u) {
    for(int v : pre[u]) {
        a[u].push_back(v);
        a[v].push_back(u);
        build(v);
    }
}

int CriticalEdge = 0;
int Num[N], Low[N], Time = 0;

void visit(int u, int p) {
    Low[u] = Num[u] = ++Time;

    for(int v : a[u]) {
        if(v != p) {
            if(Num[v] != 0)
                Low[u] = min(Low[u], Num[v]);
            else {
                visit(v, u);
                Low[u] = min(Low[u], Low[v]);

                if(Low[v] >= Num[v])
                    CriticalEdge++;
            }
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#else
    freopen("UPGRADE.inp", "r", stdin);
    freopen("UPGRADE.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    while(m--) {
        int p, q, w; cin >> p >> q >> w;
        graph[p].push_back(ii(w, q));
        graph[q].push_back(ii(w, p));
    }
    dijkstra();
    build(n);

    for(int i = 1; i <= n; i++)
        if(!Num[i]) visit(i, i);

    cout << CriticalEdge;

    return 0;
}