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):
import sys
import copy


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    wn, wm = list(map(int, readline().split()))
    inf = 10 ** 13
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, input().rstrip('\n').split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

    cwl = copy.deepcopy(wl)
    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])
    cnt = 0
    for i in range(wn):
        for j in range(wn):
            if cwl[i][j] != 10 ** 13 and cwl[i][j] != wl[i][j]:
                cnt += 1
    print(cnt // 2)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import copy


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    wn, wm = list(map(int, input().rstrip('\n').split()))

    inf = 10 ** 13
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, input().rstrip('\n').split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

    cwl = copy.deepcopy(wl)

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    cnt = 0
    for i in range(wn):
        for j in range(wn):
            if cwl[i][j] != wl[i][j] and cwl[i][j] != 10 ** 13:
                cnt += 1
    print(cnt // 2)


if __name__ == '__main__':
    solve()

Solution (Python):
N,M = map(int,input().split())
road = [[10**6]*N for i in range(N)]
tmp = []
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[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):
           road[i][j] = min(road[i][j],road[i][k] + road[k][j]) 
ans = 0
for a,b,c in tmp:
    if road[a][b] != c:
        ans += 1

print(ans)

Solution (Python):
inf = 1000 * 1000 + 10

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

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))
    e.add((b, a, c))

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

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])

res = 0
for a, b, c in e:
    for s in range(n):
        if g[s][b] == g[s][a] + c:
            res += 1
            break

print(m - res // 2)

Solution (Python):

N,M = map(int,input().split())
lis = [[float("inf")] * N for i in range(N)]
flis = [[False] * N for i in range(N)]
ans = 0

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

for i in range(M):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    lis[a][b] = c
    lis[b][a] = c

    flis[a][b] = True
    flis[b][a] = True

for k in range(N):

    for i in range(N):

        for j in range(N):

            if lis[i][j] > lis[i][k] + lis[k][j]:
                lis[i][j] = lis[i][k] + lis[k][j]

                if flis[i][j]:
                    flis[i][j] = False
                    flis[j][i] = False
                    ans += 1

print (ans)

Solution (Python):
inf = 1000 * 1000 + 10

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

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

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

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])



need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break

print(m - len(need))

Solution (Python):
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, M = IL()
abc = [IL() for _ in range(M)]

dp = [[MAX_INT]*N for _ in range(N)]
for a, b, c in abc:
  dp[a - 1][b - 1] = c
  dp[b - 1][a - 1] = c
for i in range(N):
  dp[i][i] = 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])


used = [False]*M
cnt = 0
for edge in range(M):
  a, b, c = abc[edge]
  for i in range(N):
    for j in range(N):
      if dp[i][a - 1] + c + dp[b - 1][j] == dp[i][j]:
        used[edge] = True
        cnt += 1
        break
    else:
      continue
    break


print(M - cnt)

Solution (Python):
import sys
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline
N, M = map(int, input().split())

graph = [[0 if i == j else float("inf") for i in range(N)] for j in range(N)]
for i in range(M):
    ai, bi, ci = map(int, input().split())
    graph[ai - 1][bi - 1] = ci
    graph[bi - 1][ai - 1] = ci

dist = dijkstra(graph, directed=False)

cnt = 0
for i in range(N):
    for j in range(N):
        used = False
        if i > j:
            continue
        for k in range(N):
            if graph[i][j] + dist[k][i] == dist[i][j]:
                used = True
                break
        if not used and graph[i][j] != float("inf"):
            cnt += 1
print(cnt)

Solution (Python):
import heapq
INFTY = 10**6
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b,c = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append((b,c))
    if b not in G:
        G[b] = []
    G[b].append((a,c))
F = {}
for s in range(1,N+1):
    F[s] = {}
    d = [INFTY for _ in range(N+1)]
    d[s] = 0
    hist = [0 for _ in range(N+1)]
    heap = [(0,s)]
    while heap:
        cur = heapq.heappop(heap)
        hist[cur[1]] = 1
        for x in G[cur[1]]:
            if hist[x[0]]==0:
                if d[x[0]]>cur[0]+x[1]:
                    d[x[0]] = cur[0]+x[1]
                    F[s][x[0]] = cur[1]
                    heapq.heappush(heap,(d[x[0]],x[0]))
E = []
for s in range(1,N+1):
    for i in range(1,N+1):
        if i!=s:
            cur = i
            while cur!=s:
                j = F[s][cur]
                if (cur,j) in E or (j,cur) in E:
                    break
                else:
                    E.append((cur,j))
                cur = j
print(M-len(E))

Solution (Python):
def warshall_floyd(d, next_node):
    
    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]
                    next_node[i][j] = next_node[i][k]


INF = float("inf")

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

warshall_floyd(d, next_node)

used_path = set()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        used_path.add((i, next_node[i][j]))
        used_path.add((next_node[i][j], i))

ans = m - len(used_path) // 2

print(ans)

Solution (Python):
def warshall_floyd(d, next_node):
    
    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]
                    next_node[i][j] = next_node[i][k]


INF = float("inf")

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

warshall_floyd(d, next_node)

used_path = set()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        used_path.add((i, next_node[i][j]))
        used_path.add((next_node[i][j], i))

ans = m - len(used_path) // 2

print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
e = [[0] * (N + 1) for _ in range(N + 1)]
prev = [[-1] * (N + 1) for _ in range(N + 1)]
res = 2 * M
for _ in range(M):
  a, b, c = map(int, input().split())
  d[a][b] = c
  d[b][a] = c
for k in range(1, N + 1):
  for i in range(1, N + 1):
    for j in range(1, N + 1):
      if d[i][j] > d[i][k] + d[k][j]:
        d[i][j] = d[i][k] + d[k][j]
        if prev[k][j] == -1:
          prev[i][j] = k
        else:
          prev[i][j] = prev[k][j]
for i in range(1, N):
  for j in range(i + 1, N + 1):
    s = i
    t = j
    while prev[s][t] != -1:
      p = prev[s][t]
      e[p][t] = 1
      e[t][p] = 1
      t = p
    e[s][t] = 1
    e[t][s] = 1
for i in range(1, N + 1):
  res -= sum(e[i])
print(res // 2)

Solution (Python):
n, m = map(lambda x: int(x), input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
    a[i], b[i], c[i] = map(lambda x: int(x), input().split())

def dijkstra(graph, start):
    cost = [1000*100 for _ in range(n+1)]
    fixed = [False for _ in range(n+1)]
    cost[start] = 0
    fixed[start] = True
    tmp_sta = start
    while True:
        tmp_min = 1000*100
        for i in graph[tmp_sta]:
            cost[i[0]] = min(cost[i[0]], cost[tmp_sta]+i[1])
        for i in range(1, n+1):
            if tmp_min > cost[i] and fixed[i] == False:
                tmp_min = cost[i]
                tmp_sta = i
        if tmp_min == 1000*100:
            return cost
        else:
            fixed[tmp_sta] = True
    
graph = {}
for i in range(1, n+1):
    graph[i] = []
for i in range(m):
    graph[a[i]].append((b[i], c[i]))
    graph[b[i]].append((a[i], c[i]))

cost2d = [[]]
for i in range(1, n+1):
    cost2d.append(dijkstra(graph, i))

ans = 0
for i in range(m):
    if c[i] > cost2d[a[i]][b[i]]:
        ans += 1
print(ans)

Solution (Python):
n, m = map(lambda x: int(x), input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
    a[i], b[i], c[i] = map(lambda x: int(x), input().split())

def dijkstra(graph, start, end):
    cost = [1000*100 for _ in range(n+1)]
    fixed = [False for _ in range(n+1)]
    cost[start] = 0
    fixed[start] = True
    tmp_sta = start
    while True:
        tmp_min = 1000*100
        for i in graph[tmp_sta]:
            cost[i[0]] = min(cost[i[0]], cost[tmp_sta]+i[1])
        for i in range(1, n+1):
            if tmp_min > cost[i] and fixed[i] == False:
                tmp_min = cost[i]
                tmp_sta = i
        if tmp_sta == end:
            return tmp_min
        else:
            fixed[tmp_sta] = True
    
graph = {}
for i in range(1, n+1):
    graph[i] = []
for i in range(m):
    graph[a[i]].append((b[i], c[i]))
    graph[b[i]].append((a[i], c[i]))
    
ans = 0
for i in range(m):
    if c[i] > dijkstra(graph, a[i], b[i]):
        ans += 1
print(ans)

Solution (Python):
n, m = map(lambda x: int(x), input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
    a[i], b[i], c[i] = map(lambda x: int(x), input().split())

inf = 100 * 1000
dist = [[inf for i in range(n+1)] for j in range(n+1)]
for i in range(1, n+1):
    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(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])

count = 0
for i in range(m):
    if dist[a[i]][b[i]] < c[i]:
        count += 1
print(count)

Solution (Python):
import sys
from copy import deepcopy
input = sys.stdin.readline
n,m=map(int,input().split())
d=[[100000]*n for _ in range(n)]
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a0,b0,c0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  c[i]=c0
  d[a0-1][b0-1]=c0
  d[b0-1][a0-1]=c0
for i in range(n):
  d[i][i]=0
d2=deepcopy(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])
count=0
for i in range(n):
  for j in range(i):
    if d2[i][j] != 100000 and d[i][j]!=d2[i][j]:
      count+=1
print(count)

Solution (Python):
N,M=map(int,input().split())
INF = 10**5
D=[[INF]*N for _ in range(N)]
for i in range(N):
  D[i][i]=0
path=[]
for i in range(M):
  a,b,c = map(int,input().split())
  D[a-1][b-1]=c
  D[b-1][a-1]=c
  path.append([a-1,b-1,c])
for k in range(N):
  for i in range(N-1):
    for j in range(i+1,N):
      D[i][j]=min(D[i][j],D[i][k]+D[j][k])
      D[j][i]=D[i][j]
ans=0
for a,b,c in path:
  if D[a][b]<c:
    ans+=1
print(ans)

Solution (Python):
n,m = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(m)]
g = [[10**8]*(n) for i in range(n)]
for i in range(n):
  g[i][i] = 0
for a,b,c in edge:
  g[a-1][b-1] = c
  g[b-1][a-1] = c

for k in range(n):
  for i in range(n-1):
    for j in range(i+1,n):
      if g[i][j] > g[i][k] + g[k][j]:
        g[i][j] = g[i][k] + g[k][j]
        g[j][i] = g[i][j]

ans = 0
for a,b,c in edge:
  a -= 1; b -= 1
  if a > b:
    a,b = b,a
  for i in range(n):
    if abs(g[i][a]-g[i][b]) == c:
      break
  else:
    ans += 1
print(ans)

Solution (Python):
import heapq


def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, cur_node = heapq.heappop(q)
        if dist[cur_node] < cost:
            continue
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))
    return dist


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

shortest = []
for i in range(n):
    shortest.append(dijkstra(adj, n, i))

ans = 0
for i in range(n):
    for cost, j in adj[i]:
        if cost > shortest[i][j]:
            ans += 1
print(ans // 2)

Solution (Python):
n,m=map(int,input().split())
G=[[10**18]*n for i in range(n)]
e=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
    e.append([a-1,b-1,c])
for i in range(n):
  G[i][i]=0
for k in range(n):
  for i in range(n):
    for j in range(n):
      if G[i][j]>G[i][k]+G[k][j]:
        G[i][j]=G[i][k]+G[k][j]

print(sum(c>G[a][b] for a,b,c in e))

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

dist = [[10**10 for i in range(n)]for j in range(n)]
for i in range(n):
	dist[i][i] == 0

a = [0]*m
b = [0]*m
c = [0]*m

for i in range(m):
	a[i], b[i], c[i] = map(int,input().split())
	dist[a[i]-1][b[i]-1] = c[i]
	dist[b[i]-1][a[i]-1] = 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])


res = 0
for i in range(m):
	if c[i] > dist[a[i]-1][b[i]-1]:
		res += 1

print(res)

Solution (Python):

import sys
input = sys.stdin.buffer.readline




def getlist():
	return list(map(int, input().split()))

def warshall_floyd(d, n):
    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


def main():
	n,w = map(int,input().split())
	d = [[float("inf") for i in range(n)] for i in range(n)]
	a = []
	b = []
	weight = []
	for i in range(w):
		x,y,z = map(int,input().split())
		a.append(x - 1)
		b.append(y - 1)
		weight.append(z)
		d[x - 1][y - 1] = z
		d[y - 1][x - 1] = z
		for i in range(n):
			d[i][i] = 0
	d = warshall_floyd(d, n)
	ans = 0
	for i in range(w):
		if d[a[i]][b[i]] < weight[i] :
			ans += 1
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import heapq

def dijkstra(graph, node, target):
  INF = float("inf")
  dist = [INF] * node
  dist[target] = 0
  que = [(0, target)]
  while que:
    co, one_node = heapq.heappop(que)
    for next_c, next_n in graph[one_node]:
      dist_candi = dist[one_node] + next_c
      if dist_candi < dist[next_n]:
        dist[next_n] = dist_candi
        heapq.heappush(que, (dist[next_n], next_n))
  return dist


class SetGraph:
  def __init__(self, node_num):
    self.n = node_num
    self.graph = [[] for _ in range(self.n)]

  def add_one_edge(self, start, end, cost):
    self.graph[start].append((cost, end))
    self.graph[end].append((cost, start))

  def get_graph(self):
    return self.graph 
  

n, m = map(int, input().split(" "))
graph_set = SetGraph(n)
for i in range(m):
  a, b, c = map(int, input().split(" "))
  graph_set.add_one_edge(a - 1, b - 1, c)
graph = graph_set.get_graph()

cost = []
for i in range(n):
  temp_cost = dijkstra(graph, n, i)
  cost.append(temp_cost)

result = 0
for i in range(n):
  for c, node in graph[i]:
    if cost[i][node] != c:
      result += 1

print(result // 2)

Solution (Python):
def D():
    n, m = map(int, input().split())
    a, b, c = [], [], []
    dist = [[float('inf') if i != j else 0 for j in range(n)] for i in range(n)]

    for _ in range(m):
        in_a, in_b, in_c = map(int, input().split())
        a.append(in_a - 1)
        b.append(in_b - 1)
        c.append(in_c)

    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):
        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)


if __name__ == '__main__':
    D()

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
INF=10**9
w=[[INF]*n for i in range(n)]
for i in range(n):
    w[i][i]=0
V=[]
for i in range(m):
    a,b,c=map(int,input().split())
    V.append((a-1,b-1,c))
    w[a-1][b-1]=c
    w[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            w[i][j]=min(w[i][j],w[i][k]+w[k][j])
count=0
for v in V:
    short=False
    for i in range(n):
        for j in range(i+1,n):
            if w[i][j]==w[i][v[0]]+v[2]+w[v[1]][j] or w[i][j]==w[i][v[1]]+v[2]+w[v[0]][j]:
                short=True
    if not short:
        count+=1
print(count)

Solution (Python):
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
ns = [[0] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    cs[a][b] = cs[b][a] = c
    ns[a][b] = b
    ns[b][a] = a
for k in range(n):
    for i in range(n):
        for j in range(n):
            s = cs[i][k] + cs[k][j]
            if s < cs[i][j]:
                cs[i][j] = s
                ns[i][j] = ns[i][k]
used = set()
for i in range(n):
    for j in range(i + 1, n):
        path = [i]
        while path[-1] != j:
            s = path[-1]
            t = ns[s][j]
            path.append(t)
            used.add(tuple(sorted([s, t])))
print(m - len(used))

Solution (Python):
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
es = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    es.append((a, b, c))
    cs[a][b] = cs[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cs[i][j] = min(cs[i][j], cs[i][k] + cs[k][j])
print(sum([1 for a, b, c in es if cs[a][b] != c]))

Solution (Python):
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
es = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    es.append((a, b, c))
    cs[a][b] = cs[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cs[i][j] = min(cs[i][j], cs[i][k] + cs[k][j])
res = 0
for a, b, c in es:
    if cs[a][b] != c:
        res += 1
print(res)

Solution (Python):
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
ns = [[0] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    cs[a - 1][b - 1] = cs[b - 1][a - 1] = c
    ns[a - 1][b - 1] = b - 1
    ns[b - 1][a - 1] = a - 1
for k in range(n):
    for i in range(n):
        for j in range(n):
            s = cs[i][k] + cs[k][j]
            if s < cs[i][j]:
                cs[i][j] = s
                ns[i][j] = ns[i][k]
used = set()
for i in range(n):
    for j in range(i + 1, n):
        path = [i]
        while path[-1] != j:
            s = path[-1]
            t = ns[s][j]
            path.append(t)
            used.add(tuple(sorted([s, t])))
print(m - len(used))

Solution (Python):
from collections import defaultdict
N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in range(M)]

path = defaultdict(int)
for i in range(N):
    path[i] = defaultdict(int)

for i in range(N):
    path[i][i] = []

for i in range(M):
    ABC[i][0] -= 1
    ABC[i][1] -= 1


edges = [list() for _ in range(N)]
for a,b,c in ABC:
    edges[a].append((b,c)) 
    edges[b].append((a,c)) 
inf = 100000000

for i in range(N):
    D = [inf for _ in range(N)]
    D[i] = 0
    stack = [i]
    while stack:
        vertex = stack.pop(-1)
        for b,c in edges[vertex]:
            cost = D[vertex] + c
            if cost < D[b]:
                if vertex > b:
                    path[i][b] = path[i][vertex] + [(vertex,b)]
                else:
                    path[i][b] = path[i][vertex] + [(b,vertex)]
                D[b] = cost
                stack.append(b)

counter = set()

for i in range(N):
    for j in range(N):
        for e in path[i][j]:
            counter.add(e)

print(M-len(counter))

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

def main():
    N,M = map(int,input().split())
    INF = 10**10
    l = [[INF for _ in range(N)] for _ in range(N)]
    X = [list(map(int,input().split())) for _ in range(M)]
    for i in range(M):
        l[X[i][0]-1][X[i][1]-1] = X[i][2]
        l[X[i][1]-1][X[i][0]-1] = X[i][2]
    d = deepcopy(l)
    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])

    count = 0
    for i in range(N):
        for j in range(N):
            if l[i][j] == d[i][j]:
                count += 1

    print(M-count//2)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import copy
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[float("inf")]*(N+1) for i in range(N+1)]
    ID = [[float("inf")]*(N+1) for i in range(N+1)]
    NEX = [[set() for j in range(N+1)] for i in range(N+1)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = c
        D[b][a] = c
        ID[a][b] = i
        ID[b][a] = i
        NEX[a][b].add(b)
        NEX[b][a].add(a)
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j] > D[i][k]+D[k][j]:
                    D[i][j] = D[i][k]+D[k][j]
                    NEX[i][j].clear()
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
                elif D[i][j] == D[i][k]+D[k][j] and i!=j and j!=k and k!=i and D[i][j]<float("inf"):
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i != j:
                for l in NEX[i][j]:
                    S.add(ID[i][l])
                
    
    print(M-len(S))
            
    
    
main()

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

n += 1

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

for i in range(n):
    M[i][i] = 0
for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

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

ans = 0
for i in range(m):
    if M[A[i][0]][A[i][1]] != A[i][2]:
        ans += 1
print(ans)

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

class Edge:
    def __init__(self, id, node1=-1, node2=-1, cost=-1):
        self.id = id
        self.node1 = node1
        self.node2 = node2
        self.cost = cost
    
    def next(self, num):
        if num == self.node1:
            return self.node2
        elif num == self.node2:
            return self.node1
        else:
            return False

def main():
    N, M = map(int, input().split())

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

    ans = set([i for i in range(M)])
    for start in range(N):
        q = []
        check = [False] * N
        costs = [-1] * N
        heapq.heappush(q, (0, start, None))
        used_edge = set()
        while len(q) > 0:
            cost, node, pre_edge = heapq.heappop(q)
            if check[node]:
                if costs[node] == cost:
                    used_edge.add(pre_edge)
                continue
            costs[node] = cost
            check[node] = True
            if pre_edge != None:
                used_edge.add(pre_edge)
            for edge in edges[node]:
                next_node = edge.next(node)
                if not check[next_node]:
                    heapq.heappush(q, (cost + edge.cost, next_node, edge.id))
        ans -= used_edge
    print(len(ans))




if __name__ == "__main__":
    main()

Solution (Python):
inf = 10**10
N, M = map(int, input().split())
E = []
edge = [[inf]*N for _ in range(N)]
for i in range(N):edge[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1))
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c
flag = [[False]*N for _ in range(N)]
def warshall_floyd(d):
    next_v = [[set([i]) for i in range(N)] for j in range(N)]
    for i in range(N):
        for a in range(N):
            for b in range(N):
                if d[a][b] > d[a][i]+ d[i][b]:
                    d[a][b] = d[a][i]+ d[i][b]
                    next_v[a][b] = next_v[a][i].copy()
                elif d[a][b] == d[a][i]+ d[i][b]:
                    next_v[a][b]|=next_v[a][i]
    return (next_v, d)
next_v, d = warshall_floyd(edge)    
ans = M
for a, b in E:
    if any(b in next_v[a][i] or a in next_v[b][i] for i in range(N)):
        ans -= 1
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
graph = [[INF] * n for _ in range(n)]
for i in range(n):
    graph[i][i] = 0


for a, b, c in LIR(m):
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c


dist = [[graph[i][j] for j in range(n)] for i in range(n)]




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



cnt = 0
for i in range(n):
    for j in range(i, n):
        if graph[i][j] != INF and graph[i][j] > dist[i][j]:
            cnt += 1


print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for i in range(n): A[i][i]=0
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        A[a][b]=c
        A[b][a]=c
    from copy import deepcopy
    C=deepcopy(A)
    
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])
    
    B=set()
    for s,i,j in product(range(n),repeat=3):
        if (C[i][j]!=INF) and (i!=j) and (A[s][i]+C[i][j]==A[s][j]):
            B.add((min(i,j),max(i,j)))
    print(m-len(B))

resolve()

Solution (Python):
N,M=map(int,input().split());e=[[9e9]*N for _ in range(N)];g=[[0]*N for _ in range(N)]
for _ in range(M):a,b,c=map(int,input().split());e[a-1][b-1]=e[b-1][a-1]=c
for i in range(N):
 for j in range(N):
  for k in range(N):
   if e[j][k]>e[j][i]+e[i][k]:
    e[j][k]=e[j][i]+e[i][k];g[j][k]=1
print((sum(sum(l)for l in g)+2*M-N*N)//2)