Problem:
 Score : 400 points    Problem Statement You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges. The i -th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of c_i . Here, a self-loop is an edge where a_i = b_i (1≤i≤M) , and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M) . A connected graph is a graph where there is a path between every pair of different vertices. Find the number of the edges that are not contained in any shortest path between any pair of different vertices.      Constraints  2≤N≤100   N-1≤M≤min(N(N-1)/2,1000)   1≤a_i,b_i≤N   1≤c_i≤1000  c_i is an integer.  The given graph contains neither self-loops nor double edges.  The given graph is connected.         Input The input is given from Standard Input in the following format:  N  M  a_1  b_1  c_1  a_2  b_2  c_2  :  a_M  b_M  c_M       Output Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.        Sample Input 1 3 3
1 2 1
1 3 1
2 3 3      Sample Output 1 1  In the given graph, the shortest paths between all pairs of different vertices are as follows:   The shortest path from vertex 1 to vertex 2 is: vertex 1 → vertex 2 , with the length of 1 .  The shortest path from vertex 1 to vertex 3 is: vertex 1 → vertex 3 , with the length of 1 .  The shortest path from vertex 2 to vertex 1 is: vertex 2 → vertex 1 , with the length of 1 .  The shortest path from vertex 2 to vertex 3 is: vertex 2 → vertex 1 → vertex 3 , with the length of 2 .  The shortest path from vertex 3 to vertex 1 is: vertex 3 → vertex 1 , with the length of 1 .  The shortest path from vertex 3 to vertex 2 is: vertex 3 → vertex 1 → vertex 2 , with the length of 2 .   Thus, the only edge that is not contained in any shortest path, is the edge of length 3 connecting vertex 2 and vertex 3 , hence the output should be 1 .       Sample Input 2 3 2
1 2 1
2 3 1      Sample Output 2 0  Every edge is contained in some shortest path between some pair of different vertices.

Solution (Python):
n,m = map(int,input().split())
graph = [[float("inf")]*(n+1) for _ in range(n+1)]
for i in range(m):
  a,b,c = map(int,input().split())
  graph[a][b] = c
  graph[b][a] = c

    

def dijkstra(s,cost):
  d = [float("inf")]*(n+1)
  used = [False]*(n+1)
  d[s] = 0
  
  while True:
    v = -1
    for i in range(1,n+1):
      if (not used[i]) and (v == -1):
        v = i
      elif (not used[i]) and d[i] < d[v]:
        v = i
    if v == -1:
      break
    used[v] = True
               
    for j in range(1,n+1):
      d[j] = min(d[j],d[v]+cost[v][j])
  return d

ans = 0
for i in range(1,n):
  d = dijkstra(i,graph)
  for j in range(i+1,n+1):
    if i == j:
      continue
    if graph[i][j] != float("inf") and graph[i][j] > d[j]:
      ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

n,m = map(int,input().split())
ABC = [tuple() for _ in range(m)]
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)
    ABC[i] = (a-1,b-1,c)
ans = 0
wf.build()
for a,b,c in ABC:
    ans += (c > wf.d[a][b])
print(ans)

Solution (Python):
N, M = map(int, input().split())
INF = 10**10
graph = [[INF for _ in range(N)] for _ in range(N)]

C = []
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
    C.append([a-1, b-1, c])

cnt = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if(i == j):
                graph[i][j] = 0
                continue    
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

ans = M
for u, v, w in C:
    Flg = False
    for i in range(N):
        if(graph[i][v] + w == graph[i][u]):
            Flg = True
    if Flg:
        ans -= 1
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        
        
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d

n,m = na()
g = WarshallFloyd(n)
abc = []

for i in range(m):
    a,b,c = na()
    g.add(a-1,b-1,c)
    abc.append([a-1,b-1,c])

dp = g.WarshallFloyd_search()

ans = 0
for a,b,c in abc:
    if dp[a][b] < c:
        ans += 1

print(ans)

Solution (Python):






from scipy.sparse import csr_matrix  


from scipy.sparse.csgraph import dijkstra
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
adj_mat = [[0] * N for _ in range(N)]
INF = 10 ** 9
from collections import defaultdict
from itertools import combinations
edges = defaultdict(lambda: INF)
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c
    edges[a, b] = c

adj_mat = csr_matrix(adj_mat, dtype='int')
D = dijkstra(adj_mat, directed=False)



edge_not_use = set()














for (i, j), e in edges.items():
    for s in range(N):
        d = D[s, j]
        if d == D[s, i] + e or d == D[s, j] + e:
            break
    else:
        edge_not_use.add((i, j))


print(len(edge_not_use))

Solution (Python):







from heapq import heapify, heappop, heappush, heappushpop

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


INF = 10**9 + 1


def dijkstra(adj: list, s: int, N: int):
    Color = [0] * N  
    D = [INF] * N  
    P = [None] * N  

    
    D[s] = 0  
    P[s] = None  
    PQ = PriorityQueue([(0, s)])  

    
    while PQ:  
        
        
        
        
        
        min_cost, u = PQ.pop()  

        Color[u] = 2  

        if D[u] < min_cost:
            
            continue

        
        for idx_adj_u, w_adj_u in adj[u]:
            if Color[idx_adj_u] != 2:
                
                if D[u] + w_adj_u < D[idx_adj_u]:
                    D[idx_adj_u] = D[u] + w_adj_u  
                    P[idx_adj_u] = u
                    PQ.push((D[idx_adj_u], idx_adj_u))  
                    Color[idx_adj_u] = 1

    return D, P



N, M = read_ints()
adj = [[] for _ in range(N)]  
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj[a].append((b, c))
    adj[b].append((a, c))

used_edges = set()
for s in range(N):
    _, P = dijkstra(adj, s, N)
    for i, p in enu(P):
        if p == None:
            continue
        if p > i:
            i, p = p, i
        used_edges.add((i, p))

print(M - len(used_edges))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    inf = 10**17
    

    N, W = map(int, input().split())
    
    dp = [[inf]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    abc = [list(map(int, input().split())) for _ in range(W)]
    for a,b,c in abc:
        dp[a-1][b-1] = c
        dp[b-1][a-1] = c

    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dp[i][k]==inf or dp[k][j]==inf:
                    continue
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
    
    res = 0
    for a,b,c in abc:
        for k in range(N):
            if dp[a-1][k] == c + dp[b-1][k]:
                res += 1
                break
    print(W - res)

if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
g=[[10**9]*n for i in range(n)]
edges=[]
for i in range(m):
  u,v,c=map(int,input().split())
  g[u-1][v-1]=g[v-1][u-1]=c
  edges.append((u-1,v-1,c))
for k in range(n):
  for i in range(n):
    for j in range(n):
      g[i][j]=min(g[i][j],g[i][k]+g[k][j])
cnt=0
flag=False
for u,v,c in edges:
  if g[u][v]==c:
    cnt+=1
print(m-cnt)

Solution (Python):

inf = 10 ** 10
n, m = map(int, input().split())
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    edges.append((a-1, b-1, c))

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
warshall_floyd(d)

ans = m
for u, v, c in edges:
    flg = False
    for i in range(n):
        if d[i][v] + c == d[i][u]:
            flg = True
    
    if flg:
        ans -= 1

print(ans)

Solution (Python):
def warshall_floyd():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])

N, M = map(int, input().split())
d = [[10**18]*N for _ in range(N)]

for i in range(N):
    d[i][i] = 0
    
edges = []

for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    edges.append((a-1, b-1, c))

warshall_floyd()
ans = 0

for a, b, c in edges:
    flag = True
    
    for i in range(N):
        for j in range(N):
            if d[i][a]+c+d[b][j]==d[i][j]:
                flag = False
    
    if flag:
        ans += 1

print(ans)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n,m=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]

def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


dic=defaultdict(int)
d = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(m):
    x,y,z = abc[i]
    x,y=x-1,y-1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 
tmp=warshall_floyd(d)

for i in range(m):
    a,b,c=abc[i]
    if tmp[a-1][b-1]==c:
        dic[(a,b)]+=1

print(m-len(dic))

Solution (Python):
INF=100000000
N,M=map(int,input().split())
a=[0]*1000
b=[0]*1000
c=[0]*1000
dist=[[INF for _ in range(100)] for _ in range(100)]
for i in range(M):
  a[i],b[i],c[i]=map(int,input().split())
  a[i]-=1
  b[i]-=1
for i in range(N):
  for j in range(N):
    if i==j:
      dist[i][j]=0
for i in range(M):
  dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i])
  dist[b[i]][a[i]]=min(dist[b[i]][a[i]],c[i])
for k in range(N):
  for i in range(N):
    for j in range(N):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
ans=M
for i in range(M):
  flag=False
  for j in range(N):
    if dist[j][a[i]]+c[i]==dist[j][b[i]]: flag=True
  if flag: ans-=1
print(ans)

Solution (Python):
N,M = map(int,input().split())
inf = float('inf')
D = [[inf]*N for _ in range(N)]
for i in range(N):
    D[i][i] = 0

edges = []
for _ in range(M):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c
    edges.append([a,b,c])

for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j],D[i][k] + D[k][j])


ans = 0
for e in edges:
    used = False
    for s in range(N):
        if D[s][e[0]] + e[2] == D[s][e[1]]:
            used = True
    if not used:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
inf = float('inf')
D = [[inf]*N for _ in range(N)]
for i in range(N):
    D[i][i] = 0

edges = []
for _ in range(M):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c
    edges.append([a,b,c])

for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j],D[i][k] + D[k][j])


ans = 0
for e in edges:
    used = False
    for s in range(N):
        for t in range(N):
            if D[s][e[0]] + e[2] + D[e[1]][t] == D[s][t]:
                used = True
    if not used:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
inf = 10 ** 6

d = [[inf]*N for i in range(N)]
prev = [[N]*N for i in range(N)]
vlist = [[0]*N for i in range(N)]

for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    vlist[a][b] = 1
    vlist[b][a] = 1
    d[a][b] = c
    d[b][a] = c
    prev[a][b] = a
    prev[b][a] = b







for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
                prev[i][j] = prev[k][j]

for i in range(N):
    for j in range(N):
        if prev[i][j] == i:
            vlist[i][j] = 0







count = 0
for i in range(N-1):
    for j in range(i,N):
        if vlist[i][j] == 1 and vlist[j][i] == 1:
            count += 1

print(count)

Solution (Python):
n,m= map(int,input().split())
rg = [[999999999 for _ in range(n)] for _ in range(n)]
rgflg = [[False for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b,c= map(int,input().split())
    rg[a-1][b-1] = c
    rgflg[a-1][b-1] = True
    rg[b-1][a-1] = c
    rgflg[b-1][a-1] = True
count=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if rg[i][j] > rg[i][k] + rg[k][j]:
                rg[i][j] = rg[i][k] + rg[k][j]
                if rgflg[i][j]==True or rgflg[j][i]==True:
                    rgflg[i][j]=False
                    rgflg[j][i]=False
                    count+=1
print(count)

Solution (Python):

INF = 10**19

def dijkstra_back(s,t,n,w,cost):
    prev = [s] * n 
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

N,M = map(int, input().split())

cost = [[float("inf") for i in range(N)] for j in range(N)]
edges = set()
for i in range(M):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    cost[a][b] = c
    cost[b][a] = c
    edges.add(min(a,b)*10**5 + max(a,b))

for i in range(N):
    for j in range(i+1,N):
        d = dijkstra_back(i,j,N,M,cost)
        for k in range(len(d)-1):
            a_ = min(d[k],d[k+1])
            b_ = max(d[k],d[k+1])
            X = a_*10**5+b_
            if X in edges:
                edges.remove(X)
print(len(edges))

Solution (Python):
N,M=map(int,input().split())
h=[list(map(int, input().split())) for i in range(M)]
s=[[10**6]*N for i in range(N)]
for i in h:
    s[i[0]-1][i[1]-1]=i[2]
    s[i[1]-1][i[0]-1]=i[2]
for i in range(N):
    for j in range(N):
        for k in range(N):
            s[j][k] = min(s[j][k],s[j][i] + s[i][k])
a=0
for i in h:
    if s[i[0]-1][i[1]-1]!=i[2]:
        a+=1
print(a)

Solution (Python):
N, M = map(int, input().split())

d = [[10**10]*N for _ in range(N)]

m = {}

for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    m[(a-1, b-1)] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]

ans = 0

for e in m:
    a, b = e
    if d[a][b] < m[e]:
        ans += 1

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    n,m=MI()
    dist=[[inf]*n for _ in range(n)]
    abc=[]
    for _ in range(m):
        a,b,c=MI()
        a,b=a-1,b-1
        abc.append((a,b,c))
        dist[a][b]=dist[b][a]=c
    for i in range(n):dist[i][i]=0
    for j in range(n):
        for i in range(n):
            for k in range(n):
                dist[i][k]=dist[k][i]=min(dist[i][k],dist[i][j]+dist[j][k])
    ans=0
    for a,b,c in abc:
        if dist[a][b]<c:ans+=1
    print(ans)

main()

Solution (Python):
N, M = map(int, input().split())
Map = [[int(1e18) for _ in range(N)] for __ in range(N)]
Path = [[[] for _ in range(N)] for __ in range(N)]
D = {}
for i in range(M):
  a, b, c = map(int, input().split())
  Map[a-1][b-1] = c
  Map[b-1][a-1] = c
  Path[a-1][b-1] = [a-1, b-1]
  Path[b-1][a-1] = [b-1, a-1]
  D[(a-1)*N+b-1] = 0
  D[(b-1)*N+a-1] = 0
for i in range(N):
  Map[i][i] = 0

for k in range(N):
  for i in range(N):
    for j in range(N):
      if Map[i][j] > Map[i][k] + Map[k][j]:
        Map[i][j] = Map[i][k] + Map[k][j]
        Path[i][j] = Path[i][k][:] + Path[k][j][1:]
        
for i in range(N):
  for j in range(N):
    X = Path[i][j][:]
    n = len(X)
    for k in range(n-1):
      l = X[k] * N + X[k+1]
      r = X[k+1] * N + X[k]
      if l in D:
        D[l] = 1
      if r in D:
        D[r] = 1
SUM41 = 0
for i in D:
  if D[i] == 0:
    SUM41 += 1
print(SUM41 // 2)

Solution (Python):
import sys

input=sys.stdin.readline

N,M=map(int,input().split())
hen=[]
for i in range(0,M):
    a,b,length=map(int,input().split())
    hen.append((a-1,b-1,length))

shortest=[[10**20 for i in range(0,N)] for j in range(0,N)]

for i in range(0,M):
    a,b,length=hen[i]
    shortest[a][b]=length
    shortest[b][a]=length

for k in range(0,N):
    for i in range(0,N):
        for j in range(0,N):
            shortest[i][j]=min(shortest[i][j],shortest[i][k]+shortest[k][j])

count=0
for i in range(0,M):
    a,b,length=hen[i]
    if length!=shortest[a][b]:
        count+=1

print(count)

Solution (Python):
import sys
INF = 10**10
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from functools import lru_cache
from itertools import permutations

def main():
    n,m = map(int,input().split())
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0

    edge = []
    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c
        edge.append((a,b,c))
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
    
    cnt = 0
    for e in edge:
        a,b,c = e
        flag = True
        for i in range(n):
            for j in range(n):
                if dist[i][a] + c + dist[b][j] == dist[i][j]:
                    flag = False
                    break
            if flag == False:
                break
        
        if flag:
            cnt += 1
    
    print(cnt)

if __name__=='__main__':
    main()

Solution (Python):

n, m = map(int, input().split())

d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
edge_data=[]
connect={i:[] for i in range(1,n+1)}
for i in range(m):
    x, y, z = map(int, input().split())
    
    d[x][y] = z
    d[y][x] = z
    connect[x].append(y)
    connect[y].append(x)    
    edge_data.append((x,y,z))
for i in range(n + 1):
    d[i][i] = 0  


def warshall_floyd(d):
    
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

warshall_floyd(d)


cnt=0
for some in edge_data:
    x,y,z=some[0],some[1],some[2]
    if d[x][y]<z:
        cnt+=1
print(cnt)

Solution (Python):

n, m = map(int, input().split())

d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
edge_data=[]
connect={i:[] for i in range(1,n+1)}
for i in range(m):
    x, y, z = map(int, input().split())
    
    d[x][y] = z
    d[y][x] = z
    connect[x].append(y)
    connect[y].append(x)    
    edge_data.append((x,y,z))
for i in range(n + 1):
    d[i][i] = 0  


def warshall_floyd(d):
    
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

warshall_floyd(d)


cnt=0
for some in edge_data:
    x,y,z=some[0],some[1],some[2]
    if d[x][y]<z:
        cnt+=1
print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def warshall_floyd(dp):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j])
    return dp

n, m = map(int, input().split())
d = [[float("inf")]*n for i in range(n)]

abc = [tuple(map(int,input().split())) for i in range(m)]
for a,b,c in abc:
    a,b = a-1,b-1
    d[a][b] = c
    d[b][a] = c

for i in range(n):
    d[i][i] = 0

warshall_floyd(d)

ans = m

for i, (a,b,c) in enumerate(abc):
    a,b = a-1,b-1
    for j in range(n):
        if  d[j][a] + c == d[j][b]:
            ans-=1
            break

print(ans)

Solution (Python):
inf = 10 ** 18
n, m = map(int, input().split())
d = [[inf for _ in range(n)] for _ in range(n)]
edge = [tuple(map(int, input().split())) for _ in range(m)]

for i in range(n):
    d[i][i] = 0
for a, b, c in edge:
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for a, b, c in edge:
    if d[a-1][b-1] != c:
        ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import copy

def main():
    N,M=MI()
    inf=10**10
    adj=[[inf]*N for _ in range(N)]
    for i in range(N):
        adj[i][i]=0
        
    
    for i in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        adj[a][b]=c
        adj[b][a]=c
        
    d=copy.deepcopy(adj)
    
    def warshall_floyd(d):
            
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        return d
    
    ans=0
    d=warshall_floyd(d)
    
    for i in range(N):
        for j in range(N):
            if d[i][j]!=adj[i][j] and adj[i][j]!=inf:
                ans+=1
                
    print(ans//2)
    
        
    
    
        

main()

Solution (Python):
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


n,w = map(int,input().split()) 

d = [[float("inf")]*n for i in range(n)] 

x = [0]*w
y = [0]*w
z = [0]*w
for i in range(w):
    x[i],y[i],z[i] = map(int,input().split())
    d[x[i]-1][y[i]-1] = z[i]
    d[y[i]-1][x[i]-1] = z[i]
for i in range(n):
    d[i][i] = 0 
d = warshall_floyd(d)

res = 0
for i in range(w):
    if z[i] > d[x[i]-1][y[i]-1]:
        res += 1
print(res)

Solution (Python):
from copy import deepcopy
N, M = map(int, input().split())
INF = 10**9+7
graph = [[INF for _ in range(N)] for l in range(N)]

for i in range(M):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1

  graph[b][a] = c
  graph[a][b] = c

newGraph = deepcopy(graph)

for k in range(N):
  for i in range(N):
    for j in range(N):
      newGraph[i][j] = min(newGraph[i][j], newGraph[i][k] + newGraph[k][j])

res = 0
for (i, row) in enumerate(newGraph):
  for (j, weight) in enumerate(row):
    if graph[i][j] != weight and graph[i][j] != INF:
      res += 1
print(res//2)

Solution (Python):
n, m = map(int, input().split())
INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]
tmp = []

for i in range(m):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
    tmp.append((a - 1, b - 1, c))

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ans = 0
for a, b, c in tmp:
    if c > graph[a][b]:
        ans += 1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


N, W = [int(x) for x in input().split()] 
inf = float("inf")


d = [[inf] * N for _ in range(N)]
abc = []

for _ in range(W):
    a, b, c = [int(x) for x in input().split()]
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c
    abc.append([a, b, c])


for i in range(N):
    d[i][i] = 0

d = warshall_floyd(d)
cnt = 0

for i in range(W):
    a, b, c = abc[i]
    if d[a - 1][b - 1] != c:
        cnt += 1

print(cnt)

Solution (Python):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import *
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for i,(a,b,c) in enumerate(ABC):
    data[a].append([b,c,i])
    data[b].append([a,c,i])


mlst=set()

for sp in range(1,N+1):
    visited={sp}
    dic={}
    stack=[]
    distance=[0 for i in range(N+1)]
    for p,c,i in data[sp]:
        if not c in dic:
            dic[c]=[[p,i]]
            stack.append(c)
        else:
            dic[c].append([p,i])
            stack.append(c)
    heapify(stack)
    while stack:
        m=heappop(stack)
        a,i=dic[m].pop()
        if a in visited:
            if distance[a]==m:
                mlst.add(i)
            continue
        visited.add(a)
        mlst.add(i)
        distance[a]=m
        for p,c,i in data[a]:
            if not p in visited:
                C=m+c
                heappush(stack,C)
                if C in dic:
                    dic[C].append([p,i])
                else:
                    dic[C]=[[p,i]]
print(M-len(mlst))

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

graph = [[0] * n for _ in range(n)]
for a, b, c in abc:
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

dist = floyd_warshall(csr_matrix(graph))

ans = 0
for a, b, c in abc:
    a -= 1
    b -= 1

    if dist[a][b] != c:
        ans += 1

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a[i],b[i],c[i]=map(int,input().split())
  a[i]-=1
  b[i]-=1
INF=10**18
dist=[ [INF]*n for _ in range(n)]
for i in range(n):
  dist[i][i]=0
for i in range(m):
  dist[a[i]][b[i]]=c[i]
  dist[b[i]][a[i]]=c[i]

for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
ans=m
for i in range(m):
  shortest=False
  for j in range(n):
    if dist[j][a[i]]+c[i]==dist[j][b[i]]:
      shortest=True
      break
  if shortest:
    ans-=1
print(ans)

Solution (Python):
n,m=map(int,input().split())
INF=10**18
edge=[[INF]*n for i in range(n)]
s=[]
for i in range(m):
  u,v,c=map(int,input().split())
  edge[u-1][v-1]=edge[v-1][u-1]=c
  s.append((u-1,v-1,c))
for k in range(n):
  for i in range(n):
    for j in range(n):
      edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
cnt=0
for i,j,cost in s:
  if edge[i][j]==cost:
    cnt+=1
print(m-cnt)

Solution (Python):
def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

n, m = map(int, input().split())
INF = 10**18
d = [[INF for i in range(n)] for j in range(n)]
e = [[0, 0, 0] for _ in range(m)]
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    d[a][b] = c
    d[b][a] = c

    e[i][0] = a
    e[i][1] = b
    e[i][2] = c

for i in range(n):
    d[i][i] = 0

d = warshal_floyd(d)
ans = 0
for i in range(m):
    a = e[i][0]
    b = e[i][1]
    c = e[i][2]
    for k in range(n):
        if d[a][k] == c + d[b][k]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

n, m = map(int, input().split())
INF = 10**18
d = [[INF for i in range(n)] for j in range(n)]
e = [[0, 0, 0] for _ in range(m)]
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    d[a][b] = c
    d[b][a] = c

    e[i][0] = a
    e[i][1] = b
    e[i][2] = c

for i in range(n):
    d[i][i] = 0

d = warshal_floyd(d)
ans = 0
for i in range(m):
    a = e[i][0]
    b = e[i][1]
    c = e[i][2]
    for k in range(n):
        if d[a][k] == c + d[b][k]:
            break
    else:
        ans += 1
print(ans)