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):
def dijkstra(s):
    import  heapq
    dist=[inf for i in range(n)] 
    dist[s]=0
    mirai=[True for i in range(n)] 
    mirai[s]=False

    queue=[] 
    for kyori,to in G[s]:
        heapq.heappush(queue , kyori*10**6+to)  
    while queue:
        minedge= heapq.heappop(queue)
        
        if not mirai[minedge%(10**6)]: continue
        
        v=minedge%(10**6) 
        dist[v] = minedge//(10**6) 
        mirai[v]=False
        for kyori,to in G[v]:
            if mirai[to]:
                heapq.heappush(queue, (kyori+dist[v])*(10**6)+to)
                
    return dist
n,m=map(int,input().split())
inf=10**10
G=[[] for i in range(n)]
HEN=[]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    G[a].append((c,b))
    G[b].append((c,a))
    HEN.append((a,b,c))

MIN=[[10**10]*n for i in range(n)]
for i in range(n):
    MIN[i]=dijkstra(i)
ans=0
for a,b,c in HEN:
    for s in range(n):
        if MIN[s][a]+c == MIN[s][b]:
            break
        if MIN[s][b]+c == MIN[s][a]:
            break
    else:
        ans+=1
print(ans)

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

edge = set()
INF = float('inf')
cost = [[INF]*n for _ in range(n)]
for i in range(n):
    cost[i][i] = 0
for a, b, c in abc:
    a, b = a-1, b-1
    cost[a][b] = c
    cost[b][a] = c
    edge.add((a, b, c))

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

ans = 0
for a, b, c in edge:
    if cost[a][b] < c:
        ans += 1
print(ans)

Solution (Python):
import heapq
n, m = map(int, input().split())
edges = dict()
ans = [0 for _ in range(m + 1)]
graph = [set() for _ in range(n)]


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


for i in range(n):
    done = [True for _ in range(n)]
    D = [(0, 0, i, m), ]
    heapq.heapify(D)

    while D:
        d = heapq.heappop(D)
        cost, mark, node, edge = d

        if done[node]:
            done[node] = False
            ans[edge] = 1

            for g in graph[node]:
                a, b, c = edges[g]

                if b == node:
                    a, b = b, a

                if done[b]:
                    heapq.heappush(D, (cost + c, ans[g], b, g))

print(m - (sum(ans) - 1))

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
edges = [[10**18]*N for _ in range(N)]
used = [[False]*N for _ in range(N)]

ab = []
for _ in range(M):
    a, b, c = mapint()
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c
    ab.append((a-1, b-1))

from heapq import heappop, heappush

def dijkstra(start):
    dist = [10**18]*N
    Q = [(0, start, start)]
    cnt = 0
    while Q:
        d, v, e = heappop(Q)
        if d>dist[v]:
            continue
        else:
            dist[v] = d
        cnt += 1
        used[v][e] = True
        used[e][v] = True
        for nx in range(N):
            if edges[v][nx]==10**18:
                continue
            if dist[nx] > d + edges[v][nx]:
                heappush(Q, (d + edges[v][nx], nx, v))
        if cnt==N:
            break

for i in range(N):
    dijkstra(i)
ans = 0
for a, b in ab:
    if not used[a][b]:
        ans += 1
print(ans)

Solution (Python):
import heapq
n, m = map(int, input().split())

graph = [set() for _ in range(n)]
side = dict()
ans = [0 for _ in range(m + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    t = (a - 1, b - 1, c)
    side[i] = t
    graph[a-1].add(i)
    graph[b-1].add(i)

for j in range(n):
    D = [(0, 0, j, m), ]
    heapq.heapify(D)
    done = [True for _ in range(n)]

    while D:
        d = heapq.heappop(D)
        if done[d[2]]:
            done[d[2]] = False
            ans[d[3]] = 1

            for i in graph[d[2]]:
                a, b, c = side[i]
                if b == d[2]:
                    a, b = b, a
                if done[b]:
                    heapq.heappush(D, (d[0] + c, ans[i], b, i))

print(m - (sum(ans) - 1))

Solution (Python):
INFTY = 10**5+10
N,M = map(int,input().split())
L = [list(map(int,input().split())) for _ in range(M)]
G = {i:[] for i in range(1,N+1)}
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for j in range(M):
    a,b,c = L[j]
    G[a].append(b)
    G[b].append(a)
    dist[a][b] = c
    dist[b][a] = c
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
cnt = 0
for j in range(M):
    a,b,c = L[j]
    if dist[a][b]<c:
        cnt += 1
print(cnt)

Solution (Python):
import heapq
def dijkstra(s, n, g): 
    INF = 10**18
    prev_vl = [-1]*n 
    d = [INF] * n
    d[s] = 0
    que = [] 
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue 
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                prev_vl[next_v] = v
                heapq.heappush(que, (d[next_v], next_v))
    
    
    
    
    
    
    
    
    
    

    used_edges = []
    for i in range(n):
        if i == s: continue
        used_edges.append((prev_vl[i],i))
    return d, used_edges


n,m = map(int, input().split())
g = [ [] for _ in range(n)]
edges = [ [False]*n for _ in range(n)]

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

for i in range(n):
    d, used_edges = dijkstra(i, n, g)
    for a,b in used_edges:
        edges[a][b] = False
        edges[b][a] = False

ans = 0
for i in range(n):
    for j in range(n):
        if edges[i][j]: ans += 1

print(ans//2)

Solution (Python):
import heapq

n,m=map(int,input().split())
L=[[] for i in range(n+1)]
DIC={}
for _ in range(m):
    a,b,c=map(int,input().split())
    L[a].append((b,c))
    L[b].append((a,c))
    DIC[(a,b)]=0

que=[] 


heapq.heapify(que)

for tar in range(1,n+1):
    sc=[10**8 for i in range(n+1)]
    sc[tar]=0
    pre=[tar for i in range(n+1)]
    heapq.heappush(que,(0,tar))
    while len(que)>0:
        nco,now=heapq.heappop(que)
        
        for can in L[now]:
            nex=can[0]
            cos=can[1]
            if sc[nex]>cos+nco:
                sc[nex]=cos+nco
                heapq.heappush(que,(cos+nco,nex))
                pre[nex]=now
    for i in range(1,n+1):
        if pre[i]!=i:
            a,b=i,pre[i]
            if a>b:
                a,b=b,a
            DIC[(a,b)]=1

ans=m
for val in DIC.values():
    ans-=val
print(ans)

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,m = map(int,input().split()) 
lst=[]

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

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

table=warshall_floyd(d)
ans=0

for x,y,z in lst:
    if table[x][y]!=z:
        ans+=1


print(ans)

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

from heapq import heappush, heappop
def dijkstra(n, graph, s):
    dist = [float('inf')] * n
    hq = [(0, s)]
    dist[s] = 0
    while hq:
        c, v = heappop(hq)
        if dist[v] < c:
            continue
        for t, cost in graph[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(hq, (dist[t], t))
    return dist

graph = [[] for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, c))
    graph[b].append((a, c))
    edges_used[(a, b, c)] = False
dist = [dijkstra(N, graph, i) for i in range(N)]

for edge in edges_used.keys():
    a, b, c = edge
    for i in range(N):
        if dist[i][a] == dist[i][b] + c or dist[i][b] == dist[i][a] + c:
            edges_used[edge] = True

ans = 0
for used in edges_used.values():
    if not used:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int,input().split())
E = set()
d = [[10**9]*N for k in range(N)]
for k in range(N):
    d[k][k] = 0
for k in range(M):
    a, b, c = map(int,input().split())
    E.add((a-1,b-1,c))
    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):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
ans = 0
for e in E:
    if d[e[0]][e[1]] != e[2]:
        ans += 1
print(ans)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


N,M = map(int,input().split())
f = lambda x: (int(x[0])-1,int(x[1])-1,int(x[2]))
edges = list(f(input().split()) for _ in range(M))

g = np.zeros((N,N), dtype=float)

for a,b,c in edges:
    g[a,b] = c
    g[b,a] = c

floyd_warshall(g, directed=False, overwrite=True)

res = sum(int(g[a,b] != c) for a,b,c in edges)
print(res)

Solution (Python):
N,M = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
ds = [[INF]*N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    ds[a][b] = ds[b][a] = c

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

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

Solution (Python):
n,m = map(int,input().split())
g = []
dp = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    dp[i][i]=0
for _ in range(m):
    a,b,c = map(int,input().split())
    g.append((a-1,b-1,c))
    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):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])

cnt = 0

for a,b,c in g:
    f = True
    for i in range(n):
        if dp[i][a]+c==dp[i][b]:
            f = False
            break
    if f:
        cnt += 1
print(cnt)

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

inf = 10 ** 9 + 7
dp = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dp[a][b] = c
    dp[b][a] = c

old_dp = copy.deepcopy(dp)
check = [[False] * N for _ in range(N)]
count = 0
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])

count = 0
for i in range(N):
    for j in range(N):
        if old_dp[i][j] != dp[i][j] and old_dp[i][j] != inf:
            count += 1

print(count // 2)

Solution (Python):
import sys
import heapq

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10 ** 18


def warshall_floyd(V, cost):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])


def main():
    N, M = in_nn()
    cost = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        cost[i][i] = 0

    edge = []
    for i in range(M):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge.append((min(a, b), max(a, b), c))
        cost[a][b] = c
        cost[b][a] = c

    warshall_floyd(N, cost)

    ans = set()
    for i in range(N):
        for j in range(i + 1, N):
            for e in edge:
                a, b, c = e
                if cost[i][j] == cost[i][a] + c + cost[b][j]:
                    ans.add((a, b))
                elif cost[i][j] == cost[i][b] + c + cost[a][j]:
                    ans.add((a, b))

    print(M - len(ans))


if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int,input().split())
DP = [[float('inf')]*N for _ in range(N)]
B = []
for i in range(N):
  DP[i][i] = 0
for _ in range(M):
  a,b,c = map(int,input().split())
  DP[a-1][b-1] = c
  DP[b-1][a-1] = c
  B.append([a-1,b-1,c])
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])   
ans = 0
for i in range(M):
    a,b,c = B[i]
    for j in range(N):
        if DP[j][b] == DP[j][a] + c:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
d = [[10**10]*N for i in range(N)]
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
  d[a[i]][b[i]] = c[i]
  d[b[i]][a[i]] = c[i]
for i in range(N):
  d[i][i] = 0

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

ans = M
for i in range(M):
  tmp = 0
  for j in range(N):
    if d[j][a[i]] + c[i] == d[j][b[i]]:
      tmp = 1
  ans -= tmp
print(ans)

Solution (Python):
import heapq

def dijkstra(s):
    inf = 1145141919810
    dist = [inf] * v
    dist[s] = 0
    c = [0] * v
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist

n, m = map(int, input().split())
v = n
G = [[] for _ in range(v)]
E = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append([b, c])
    G[b].append([a, c])
    E.append([a, b, c])
mindist = [dijkstra(i) for i in range(v)]
ans = m
for e in E:
    for i in range(n):
        if mindist[i][e[0]] - mindist[i][e[1]] == e[2]:
            ans -= 1
            break
print(ans)

Solution (Python):
import heapq

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

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

used=set()

for i in range(n):
    q=[(0,i,-1)]
    dist=[10**10]*n
    dist[i]=0
    edge=[0]*n

    while len(q)>0:
        d,u,v=heapq.heappop(q)

        if d>dist[u]:
            continue

        edge[u]=v

        for w,nd in g[u]:
            tmp=nd+dist[u]
            if tmp<dist[w]:
                dist[w]=tmp
                heapq.heappush(q,(tmp,w,u))
    
    for u,v in enumerate(edge):
        if v==-1:
            continue
        used.add((max(u,v),min(u,v)))

print(m-len(used))

Solution (Python):
N, M = map(int, input().split())
Edge = [tuple(map(int, input().split())) for _ in range(M)]

import numpy as np
Graph = np.array([[0 if i == j else np.inf for i in range(N)] for j in range(N)])
for a,b,c in Edge:
    Graph[a-1,b-1] = c
from scipy.sparse.csgraph import dijkstra 
Graph = dijkstra(Graph,directed=False)
ans = 0
for a,b,c in Edge:
    if Graph[a-1,b-1] != c:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
edges = [(i - 1, j - 1, c) for i, j, c in edges]

INF = int(10000)

dp = [[INF for _ in range(N)] for _ in range(N)]
for i, j, cost in edges:
    dp[i][j] = cost
    dp[j][i] = cost

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            if dp[i][k] != INF and dp[k][j] != INF:
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

count = 0
for i, j, cost in edges:
    if dp[i][j] < cost:
        count += 1

print(count)

Solution (Python):







INF = float("inf")
import copy

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



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

edges = []
for i in range(m):
    u, v, w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
    edges.append((u-1,v-1))
for i in range(n):
    d[i][i] = 0 

fwd = warshall_floyd(d)   

ret = 0
for u,v in edges:
    if fwd[u][v] < d[u][v]:
        ret += 1
print(ret)

Solution (Python):
Node,Path = map(int,input().split())
ad_mat = [[float('inf')]*Node for _ in range(Node)]
path_ls = [[0,0,0] for _ in range(Path)]
for i in range(Path):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c
    path_ls[i] = a-1,b-1,c
for i in range(Node):
    ad_mat[i][i] = 0

for stop in range(Node):
    for start in range(Node):
        for end in range(Node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = 0
for a,b,cost in path_ls:
    if cost > ad_mat[a][b]:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
conns = [tuple(map(int, input().split())) for _ in range(M)]
cost = [[float("INF")]*N for _ in range(N)]


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


for a,b,c in conns:
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c


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


cnt = 0
for a,b,c in conns:
  if c > cost[a-1][b-1]:
    cnt += 1

print(cnt)

Solution (Python):




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

INF = float('inf')
d = [[INF for _ in range(n)] for _ in range(n)]
for a,b,c in e:
  d[a][b] = c
  d[b][a] = c
for i in range(n):
  d[i][i] = 0
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j] = min(d[i][k]+d[k][j],d[i][j])
ans = 0
for a,b,c in e:
  if d[a][b] < c:
    ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
to = [[float("INF")] * N for i in range(N)]
aa = []

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

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

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



c = 0
for i in range(M):
    for j in range(N):
        if to[j][aa[i][1]] == to[j][aa[i][0]] + aa[i][2]:
            c += 1
            break


print(M - c)

Solution (Python):
N,M = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
ds = [[INF]*N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    ds[a][b] = ds[b][a] = c

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

ans = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    if ds[a][b] < c:
        ans += 1
print(ans)

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

G = [[] for _ in range(N)]
INF = 10**9
D = [[ INF for _ in range(N)] for _ in range(N)]
for i in range(N):
  D[i][i] = 0

E = []
for _ in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  G[a].append((b,c))
  G[b].append((a,c))
  D[a][b] = c
  D[b][a] = c
  E.append((a,b,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]
        D[j][i] = D[i][k] + D[k][j]
  
ans = 0
for a,b,c in E:
  flg = False
  for i in range(N):
    if D[i][a] + c == D[i][b]:
      flg = True
      break
   
  if not flg:
    ans += 1
    
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
INF = 10**18

def main():
    N, M = map(int, input().split())
    repn = [[] for _ in range(N)]
    edge = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        repn[a - 1].append((c, b - 1))
        repn[b - 1].append((c, a - 1))
        edge.append((a - 1, b - 1, c))

    
    dist = [[INF] * N for _ in range(N)]
    for i in range(N): dist[i][i] = 0
    for i in range(N):
        for cost, j in repn[i]: dist[i][j] = cost

    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 = 0
    for a, b, c in edge:
        no_need = True
        for i in range(N):
            for j in range(N):
                if dist[i][j] > dist[i][a] + (c - 1) + dist[b][j]:
                    no_need = False
                    break
        if no_need: ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
dis = [[float("inf") for i in range(n)] for j in range(n)]
for i in range(n):
    dis[i][i] = 0
abc = []
for i in range(m):
    a, b, c = map(int, input().split())
    abc.append([a, b, c])
    dis[a-1][b-1] = c
    dis[b-1][a-1] = c
def warshall_floyd(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis1 = dis[i][j]
                dis2 = dis[i][k] + dis[k][j]
                dis[i][j] = min(dis1, dis2)
    return dis
data = warshall_floyd(dis)
ans = 0
for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    for j in range(n):
        if c + data[b-1][j] == data[a-1][j]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
N, M = (int(x) for x in input().split())
graph = [[1000] * N for _ in range(N)]
before = []
for _ in range(M):
    a,b,c = (int(x) for x in input().split())
    before.append((a-1,b-1,c))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

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

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

ans = 0
for x in before:
    if graph[x[0]][x[1]] != x[2]:
        ans += 1
print(ans)

Solution (Python):
import heapq


def dijkstra(s):
    dist[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if (dist[v] < p[0]):
            continue
        for e in graph[v]:
            if dist[e[0]] > dist[v] + e[1]:
                dist[e[0]] = dist[v] + e[1]
                prev[e[0]] = v
                heapq.heappush(que, (dist[e[0]], e[0]))


def get_path(t):
    path = []
    while t != -1:
        path.append(t)
        t = prev[t]
    path = path[::-1]
    return path


N, W = map(int, input().split())
graph = [[] for i in range(N)]
edges = {}
for i in range(W):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append((y, z))
    graph[y].append((x, z))
    edges[(x, y)] = True

for st in range(N):
    dist = [float("inf")] * N
    prev = [-1] * N
    dijkstra(st)
    for i in range(N):
        gp = get_path(i)
        for i in range(1, len(gp)):
            edges[(gp[i-1], gp[i])] = False

print(sum(edges.values()))

Solution (Python):
n, m = map(int, input().split())
inf = float("inf")
edges = [[inf]*n for _ in range(n)]
path = [[inf]*n for _ in range(n)]
edges_list = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a][b] = c
    edges[b][a] = c
    path[a][b] = c
    path[b][a] = c
    edges_list.append((a, b))

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

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

count = 0
for a, b in edges_list:
    if path[a][b] < edges[a][b]:
        count += 1

print(count)

Solution (Python):
from scipy.sparse.csgraph import *
import numpy as np
N,M = map(int,input().split())
E = [list(map(int,input().split())) for m in range(M)]
G = np.zeros((N,N))
ans = 0

for a,b,c in E:
  G[a-1][b-1] = c
  G[b-1][a-1] = c

F = shortest_path(G).astype(int)
for a,b,c in E:
  if F[a-1][b-1]!=c:
    ans+=1

print(ans)

Solution (Python):
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        i -= 1
        j -= 1
        tree[i].append((k, j))
        tree[j].append((k, i))

    
    import heapq

    ans = 0
    for i in range(n):
        for j in tree[i]:
            seen = [0] * n
            goal = j[1]
            base = j[0]
            seen[i] = 1
            todo = []
            heapq.heapify(todo)
            for k in tree[i]:
                if k[0] < base and k != j:
                    heapq.heappush(todo, k)
            while len(todo) > 0:
                k = heapq.heappop(todo)
                if k[1] == goal:
                    if k[0] < base:
                        ans += 1
                    break
                seen[k[1]] = 1
                for l in tree[k[1]]:
                    if seen[l[1]] == 0 and k[0] + l[0] < base:
                        heapq.heappush(todo, (k[0] + l[0], l[1]))

    print(ans // 2)

main()

Solution (Python):
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        i -= 1
        j -= 1
        tree[i].append((k, j))
        tree[j].append((k, i))

    
    import heapq
    from numpy import zeros

    ans = 0
    for i in range(n):
        for j in tree[i]:
            seen = zeros(n)
            goal = j[1]
            base = j[0]
            seen[i] = 1
            todo = []
            heapq.heapify(todo)
            for k in tree[i]:
                if k[0] < base and k != j:
                    heapq.heappush(todo, k)
            while len(todo) > 0:
                k = heapq.heappop(todo)
                if k[1] == goal:
                    if k[0] < base:
                        ans += 1
                    break
                seen[k[1]] = 1
                for l in tree[k[1]]:
                    if seen[l[1]] == 0 and k[0] + l[0] < base:
                        heapq.heappush(todo, (k[0] + l[0], l[1]))

    print(ans // 2)

main()

Solution (Python):
import sys

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

memo = [[sys.maxsize]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
  memo[i][i] = 0

lst = []
for _ in range(M):
  a,b,c = map(int, input().split())
  memo[a][b] = c
  memo[b][a] = c
  lst.append((a,b,c))
  
for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      memo[i][j] = min(memo[i][j], memo[i][k] + memo[k][j])
      
cnt = 0
for a,b,c in lst:
  if memo[a][b] < c:
    cnt += 1
    
print(cnt)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        cost[i][i] = 0

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

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

    res = 0
    for d, x, y in edge:
        if cost[x][y] < d:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):

import sys 
from heapq import heappush, heappop
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

V,E = map(int, readline().split())
edges = [[] for _ in range(V+1)]

INF = 10**31

for _ in range(E):
    x,y,t = map(int, readline().split())
    edges[x].append((t,y))
    edges[y].append((t,x))
    

def dijkstra(q,dist,prev):
    while q:
        cost, v_from = heappop(q)
        if dist[v_from] < cost:
            continue
        for _cost,v_to in edges[v_from]:
            newcost = cost+_cost
            if newcost < dist[v_to]:
                prev[v_to] = v_from
                dist[v_to] = newcost 
                heappush(q,(newcost,v_to))

pp = []
for i in range(1,V+1): 
    for j in range(i+1,V+1):
        dist = [INF]*(V+1) 
        dist[i] = 0 
        prev=[None]*(V+1) 
        q = [(0,i)]
        dijkstra(q,dist,prev)
        p = [j]
        while prev[p[-1]]!=None:
            x,y = p[-1],prev[p[-1]]
            if x > y:
                x,y = y,x
            pp.append((x,y))
            p.append(prev[p[-1]])

print(E - len(set(pp)))