#include <cstdio> #include <ctime> #include <cstring> #include <vector> using namespace std; #define maxn 250010 int n, m; int a[maxn], b[maxn], c[maxn], f[maxn]; vector<int> v[maxn], vi[maxn]; int q[maxn], q0; int cost[maxn]; void df(int nod) { f[nod]=1; int fiu; for(int i=0; i<v[nod].size(); ++i) { fiu=b[v[nod][i]]; q[++q0]=v[nod][i]; if(!f[fiu]) df(fiu); } } void df2(int nod) { f[nod]=1; int fiu; for(int i=0; i<vi[nod].size(); ++i) { fiu=a[vi[nod][i]]; if(!f[fiu]) df2(fiu); } } int main() { clock_t st = clock(); scanf("%d%d", &n, &m); if(m>250000) return 11; for(int i=1; i<=m; ++i) { scanf("%d%d%d", &a[i], &b[i], &c[i]); v[a[i]].push_back(i); vi[b[i]].push_back(i); } clock_t end = clock(); double elapsed_secs = double(end - st) / CLOCKS_PER_SEC; for(int i=1; i<=n; ++i) { if(!f[i]) df(i); } int pas=0; while(pas<n) { for(int i=1; i<=q0; ++i) cost[b[q[i]]]=min(cost[a[q[i]]]+c[q[i]], cost[b[q[i]]]); ++pas; } memset(f, 0, sizeof(f)); for(int i=1; i<=q0; ++i) if(cost[b[q[i]]] > cost[a[q[i]]]+c[q[i]] && f[a[q[i]]]==0) df2(a[q[i]]); int sol=0; for(int i=1; i<=n; ++i) sol+=f[i]; printf("%d\n", sol); return 0; }