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, raw_input().split())
X = []
for _ in range(M):
    a, b, c = map(int, raw_input().split())
    X.append((a-1, b-1, c))

INF = 100000000
D = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for a, b, c in X:
    D[a][b] = c
    D[b][a] = 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 X:
    if D[a][b] != c:
        ans += 1
print ans

Solution (Python):
N,M = map(int, raw_input().split())
EDGES = {}
d = [[float('inf') for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int, raw_input().split())
  a -= 1
  b -= 1
  EDGES[(min(a,b),max(a,b))] = c
  d[a][b] = c
  d[b][a] = 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]

unused = 0
for e,v in EDGES.items():
  if v != d[e[0]][e[1]]:
    unused += 1
print unused

Solution (Python):
N,M = map(int, raw_input().split())
EDGES = {}
d = [[float('inf') for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int, raw_input().split())
  a -= 1
  b -= 1
  EDGES[(min(a,b),max(a,b))] = c
  d[a][b] = c
  d[b][a] = 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]

unused = 0
for j in range(N):
  for i in range(j):
    if((i,j) in EDGES and EDGES[(i,j)] != d[i][j]):
      unused += 1
print unused

Solution (Python):
import numpy as np
INF = 10**10
N, M = map(int, raw_input().split())
G = [map(int, raw_input().split()) for i in range(M)]
d = np.full((N+1, N+1), INF)
for i in range(N+1):
    d[i, i] = 0
for u, v, c in G:
    d[u, v] = d[v, u] = c
for u in range(N+1):
    for s in range(N+1):
        for t in range(N+1):
            d[s, t] = d[t, s] = min(d[s, t], d[s, u] + d[u, t])
ans = 0
for u, v, c in G:
    if c > d[u, v]:
        ans += 1
print ans

Solution (Python):
import sys

inf = 1<<60

def solve():
    N, M = map(int, sys.stdin.readline().split())

    cost = [[inf]*N for i in range(N)]

    for mi in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1
        cost[a][b] = cost[b][a] = c

    dist = [[0]*N for i in range(N)]

    for i in range(N):
        for j in range(i + 1, N):
            dist[i][j] = dist[j][i] = cost[i][j]

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

    ans = 0

    for i in range(N):
        for j in range(i + 1, N):
            if cost[i][j] < inf and cost[i][j] != dist[i][j]:
                ans += 1

    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
N, M = map(int, input().split())
inf = 10**6
abc = []
d = [[inf]*N for i in range(N)]
for i in range(M):
	a, b, c = map(int, input().split())
	d[a-1][b-1] = c
	d[b-1][a-1] = c
	abc.append((a-1,b-1,c))

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 i in range(M):
	a, b, c = abc[i]
	if d[a][b] < inf and d[a][b] < c:
		ans += 1
print(ans)

Solution (Python):

INF=10**10

def main():
    
    n,m=list(map(int,input().split()))
    a=[0 for _ in range(m)]
    b=[0 for _ in range(m)]
    c=[0 for _ in range(m)]
    d=[[INF for i in range(n)] for i in range(n)]
    for i in range(m):
        a[i],b[i],c[i]=list(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 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])
                d[j][i]=d[i][j]
    ans=0
    for j in range(m):
        temp=1
        for i in range(n):
            if d[i][b[j]]==d[i][a[j]]+c[j]:
                temp=0
                break
        ans+=temp
    print(ans)
    
    
    
        
        
    
if __name__=="__main__":
    main()

Solution (Python):
from heapq import heappop, heappush

n, m = map(int, input().split())
links = [set() for _ in range(n)]
link_list = []
for _ in range(m):
    s, t, c = map(int, input().split())
    s, t = s - 1, t - 1
    link_list.append((s, t, c))
    links[s].add((c, t))
    links[t].add((c, s))

result = 0
for s, t, limit in link_list:
    queue = [(0, s)]
    visited = set()
    while queue:
        c, v = heappop(queue)
        if c >= limit:
            break
        if v == t:
            result += 1
            break
        if v in visited:
            continue
        visited.add(v)
        for nc, nv in links[v]:
            if nv in visited:
                continue
            if v == s and nv == t:
                continue
            heappush(queue, (c + nc, nv))
print(result)

Solution (Python):
import heapq as hq

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

costs = dict()
adj = [list() for _ in range(N)]

e = lambda a,b: (a,b) if a<=b else (b,a)

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

max_dist = sum(costs.values())+1
used_edge = set()

for s in range(N):
  q = [(0,s)]
  dist = [max_dist]*N
  dist[s] = 0

  while q:
    c, u = hq.heappop(q)
    if c > dist[u]:
      continue

    for v in adj[u]:
      ee = e(u,v)
      if dist[v] > dist[u] + costs[ee]:
        dist[v] = dist[u] + costs[ee]
        hq.heappush(q, (dist[v], v))

  for t in adj[s]:
    if costs[e(s,t)] == dist[t]:
      used_edge.add(e(s,t))

print(len(costs.keys()-used_edge))

Solution (Python):
import copy
from itertools import product as prod

n, m = [int(x) for x in input().split()]

wait = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(n):
    wait[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    wait[a-1][b-1] = c
    wait[b-1][a-1] = c

dist = copy.deepcopy(wait)
for k, i, j in prod(range(n), range(n), range(n)):
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    dist[j][i] = min(dist[j][i], dist[j][k] + dist[k][i])

ans = 0
for i, j in prod(range(n), range(n)):
    if not wait[i][j] == float("inf") and dist[i][j] < wait[i][j]:
        ans += 1

print(ans // 2)

Solution (Python):
INF = 123456789

def main():
    n,m = map(int,input().split())

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

    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    c = [0 for _ in range(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]] = min(d[a[i]][b[i]], c[i])
        d[b[i]][a[i]] = min(d[b[i]][a[i]], c[i])

    
    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 i in range(m):
        found = 1
        for j in range(n):
            if d[j][a[i]] + c[i] == d[j][b[i]]:
                found = 0
                break
        ans += found
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
INF = 123456789

def main():
    n,m = map(int,input().split())

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

    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    c = [0 for _ in range(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]] = min(d[a[i]][b[i]], c[i])
        d[b[i]][a[i]] = min(d[b[i]][a[i]], c[i])

    
    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 i in range(m):
        found = 1
        for j in range(n):
            if d[j][a[i]] + c[i] == d[j][b[i]]:
                found = 0
                break
        ans += found
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import queue

INF = 123456789

def main():
    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):
        d = [INF for _ in range(n)]
        par = [-1 for _ in range(n)]

        
        que = queue.PriorityQueue()
        d[i] = 0
        que.put((0,i))
        while not que.empty():
            p = que.get()
            v = p[1]
            if d[v] < p[0]:
                continue
            for (to,cost) in G[v]:
                if d[to] > d[v]+cost:
                    d[to] = d[v]+cost
                    par[to] = v
                    que.put((d[to],to))

        for j in range(n):
            if i != j:
                a,b = j,par[j]
                if a>b:
                    a,b = b,a
                used.add((a,b))

    print(m - len(used))

if __name__ == '__main__':
    main()

Solution (Python):
import queue

INF = 123456789

def main():
    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):
        d = [INF for _ in range(n)]
        par = [-1 for _ in range(n)]

        
        que = queue.PriorityQueue()
        d[i] = 0
        que.put((0,i))
        while not que.empty():
            p = que.get()
            v = p[1]
            if d[v] < p[0]:
                continue
            for (to,cost) in G[v]:
                if d[to] > d[v]+cost:
                    d[to] = d[v]+cost
                    par[to] = v
                    que.put((d[to],to))

        for j in range(n):
            if i != j:
                a,b = j,par[j]
                if a>b:
                    a,b = b,a
                used.add((a,b))

    print(m - len(used))

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int,raw_input().split())
INF = 10 ** 8
cost = [[INF for j in xrange(N+10)] for i in xrange(N+10)]
E = [[INF for j in xrange(N+10)] for i in xrange(N+10)]
for _ in xrange(M):
    a,b,c = map(int,raw_input().split())
    a -= 1
    b -= 1
    cost[a][b] = c
    cost[b][a] = c
    E[a][b] = c
    E[b][a] = c
for v in xrange(N):
    cost[v][v] = 0
for k in xrange(N):
    for i in xrange(N):
        for j in xrange(N):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
ans = 0
for a in xrange(N):
    for b in xrange(a+1,N):
        if E[a][b] == INF:
            continue
        OK = False
        for s in xrange(N):
            for t in xrange(s+1,N):
                if cost[s][a] + E[a][b] + cost[b][t] == cost[s][t]:
                    OK = True
            if OK:
                break
        if not OK:
            ans += 1
print ans

Solution (Python):


import sys

def main(argv):
    line = sys.stdin.readline().rstrip("\n")

    while line:
        n, m = line.split()
        n = int(n)
        m = int(m)

        edges = []
        path = [[-1 for i in xrange(n)] for i in xrange(n)]
        distance = [[1001 for i in xrange(n)] for i in xrange(n)]
        for i in xrange(m):
            a, b, c = raw_input().split()
            a = int(a) - 1
            b = int(b) - 1
            c = int(c)
            distance[a][b] = c
            distance[b][a] = c
            edges.append((a,b))

        for i in xrange(n):
            distance[i][i] = 0

        for k in xrange(n):
            for i in xrange(n):
                for j in xrange(n):
                    candidate = distance[i][k] + distance[k][j]
                    if candidate < distance[i][j]:
                        distance[i][j] = candidate
                        path[i][j] = k

        counter = 0
        for (x, y) in edges:
            if path[x][y] != -1:
                counter += 1
        print counter

        line = sys.stdin.readline().rstrip("\n")

if __name__ == "__main__":
    main(sys.argv)

Solution (Python):


MAX = 9999 

n, m = map(int, input().split())
cost = []

dist = [[MAX] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
    
for _ in range(m):
    cost.append(list(map(int, input().split())))

for a, b, c in cost:
    dist[a-1][b-1] = c
    dist[b-1][a-1] = 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])

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

Solution (Python):
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

d = [[float('inf') for i in range(n)] for j in range(n)]

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

for i in range(m):
    d[a[i]][b[i]] = c[i]
    d[b[i]][a[i]] = c[i]

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

ans = m
for i in range(m):
    f = False
    for j in range(n):
        if d[j][b[i]] == c[i] + d[j][a[i]]:
            f = True

    if f:
        ans -= 1

print(ans)

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

dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
  dist[i][i] = 0
for _ in range(m):
  abc.append(list(map(int,input().split())))

for a,b,c in abc:
  dist[a-1][b-1] = c
  dist[b-1][a-1] = 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])

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

print(ans)

Solution (Python):
INF = 1000000

N, M = map(int, raw_input().split(" "))

dat = [[INF for _ in xrange(N)] for _ in xrange(N)]
isMinimal = [[True for _ in xrange(N)] for _ in xrange(N)]

for i in xrange(N):
    dat[i][i] = 0

a = [0 for _ in xrange(M)]
b = [0 for _ in xrange(M)]
c = [0 for _ in xrange(M)]
for i in xrange(M):
    a[i], b[i], c[i] = map(int, raw_input().split(" "))
    a[i] -= 1
    b[i] -= 1
    dat[a[i]][b[i]] = c[i]
    dat[b[i]][a[i]] = c[i]

for k in xrange(N):
    for i in xrange(N):
        for j in xrange(N):
            if dat[i][j] > dat[i][k] + dat[k][j]:
                dat[i][j] = dat[i][k] + dat[k][j]
                isMinimal[i][j] = False

res = 0
for i in xrange(M):
        res += 0 if isMinimal[a[i]][b[i]] else 1

print res

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v,d])
        self.e[v].append([u,d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s, t):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            if u == t:
                return d[t]
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return None


def main():
    n,m = LI()
    dk = Dijkstra()
    t = []
    r = 0
    for _ in range(m):
        a,b,c = LI()
        dk.add(a,b,c)
        t.append([a,b,c])
    for a,b,c in t:
        d = dk.search(a,b)
        if d < c:
            r += 1
    return r


print(main())

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

my_input = lambda : map(int, input().split(" "))

N, M = my_input()
dist = 100 * 1000 * (np.ones([N, N]) - np.eye(N)).astype(int)

edges = []
for i in range(M):
    a, b, c = my_input()
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
    edges.append((a, b, c))

dist = dijkstra(dist, directed=False)
print(len([e for e in edges if e[2] != dist[e[0]-1][e[1]-1]]))

Solution (Python):



MAXI = 999999999


N, M = map(int, input().split())
cost = [[-1 for i in range(N)] for j in range(N)]

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


dist = [[MAXI for i in range(N)] for j in range(N)]


for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]


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 i in range(N):
    for j in range(i, N):
        
        if cost[i][j] != -1 and cost[i][j] != dist[i][j]:
            ans += 1

print(ans)

Solution (Python):


MAXI = 999999999


N, M = map(int, input().split())
cost = [[-1 for i in range(N)] for j in range(N)]

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


dist = [[MAXI for i in range(N)] for j in range(N)]


for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]


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 i in range(N):
    for j in range(i, N):
        if cost[i][j] != -1: 
            flag = 1

            for k in range(N):
                for l in range(k + 1, N):
                    
                    if dist[k][l] == dist[k][i] + cost[i][j] + dist[j][l]:
                        flag = 0
                        break
            
            
            ans += flag


print(ans)

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

dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    abc.append(list(map(int, input().split())))

for a, b, c in abc:
    dist[a-1][b-1] = c
    dist[b-1][a-1] = 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])

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

print(ans)

Solution (Python):
n, m = map(int, input().split())
abc = []
dis = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
    abc.append(list(map(int, input().split())))

for a, b, c in abc:
    dis[a-1][b-1] = c
    dis[b-1][a-1] = c

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

count = 0
for a, b, c in abc:
    if c > dis[a-1][b-1]:
        count += 1

print(count)

Solution (Python):


import collections
import itertools


INF = 10 ** 8
UNDEF = -1


def floyd_warshall(num_vs, edges):
    n = num_vs
    dist = [[INF for _ in range(n)] for _ in range(n)]
    for u in range(n):
        dist[u][u] = 0
    for (u, v), c in edges.items():
        dist[u][v] = c
    for t, u, v in itertools.product(range(n), repeat=3):
        nl = dist[u][t] + dist[t][v]
        if nl < dist[u][v]:
            dist[u][v] = nl
    return dist


def main():
    n, m = (int(x) for x in input().split())
    edges = dict()
    used = dict()
    for _ in range(m):
        a, b, c = (int(x) for x in input().split())
        a -= 1
        b -= 1
        edges[(a, b)] = c
        edges[(b, a)] = c
        used[(a, b)] = False
    dist = floyd_warshall(n, edges)
    ans = 0
    for (u, v), c in edges.items():
        if u < v:
            if dist[u][v] != c:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def used(dp,u,v,w):
    n=len(dp)
    for i in range(n):
        for j in range(i+1,n):
            if dp[i][j]==dp[i][u]+w+dp[v][j] or dp[i][j]==dp[i][v]+w+dp[u][j]:
                return True
    return False

while 1:
    try:
        n,m=map(int,input().split())
        es=[]
        for _ in range(m):
            u,v,w=map(int,input().split())
            es.append((u-1,v-1,w))
    except: break

    dp=[[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=0
    for u,v,w in es:
        dp[u][v]=dp[v][u]=w
    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])
    print(sum(int(not used(dp,u,v,w)) for u,v,w in es))

Solution (Python):


import collections
import itertools


INF = 10 ** 8
UNDEF = -1


def floyd_warshall_undirected(num_vs, edges):
    n = num_vs
    dist = [[INF for _ in range(n)] for _ in range(n)]
    pred = [[UNDEF for _ in range(n)] for _ in range(n)]
    for u in range(n):
        dist[u][u] = 0
    for (u, v), c in edges.items():
        dist[u][v] = c
        dist[v][u] = c
        pred[u][v] = u
        pred[v][u] = v
    for t, u, v in itertools.product(range(n), repeat=3):
        nl = dist[u][t] + dist[t][v]
        if nl < dist[u][v]:
            dist[u][v] = nl
            pred[u][v] = pred[t][v]
    return dist, pred


def construct_shortest_path(s, t, pred):
    path = collections.deque()
    path.appendleft(t)
    while t != s:
        t = pred[s][t]
        path.appendleft(t)
    return list(path)


def main():
    n, m = (int(x) for x in input().split())
    edges = dict()
    used = dict()
    for _ in range(m):
        a, b, c = (int(x) for x in input().split())
        a -= 1
        b -= 1
        a, b = min(a, b), max(a, b)
        edges[(a, b)] = c
        used[(a, b)] = False
    _, pred = floyd_warshall_undirected(n, edges)
    for s in range(n):
        for t in range(s + 1, n):
            path = construct_shortest_path(s, t, pred)
            for u, v in zip(path[:-1], path[1:]):
                u, v = min(u, v), max(u, v)
                used[(u, v)] = True
    ans = m - sum(used.values())
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
A = [0 for i in range(M)]
B = [0 for i in range(M)]
C = [0 for i in range(M)]
dist = [[float('inf') for j in range(N)] for i in range(N)]
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])

count = 0
for i in range(M):
	if dist[A[i]-1][B[i]-1] < C[i]:
		count = count+1

print(count)

Solution (Python):
[N, M] = [ int(i) for i in raw_input().split() ]
INF = int(1e9)
G = [ [ 0 if i==j else INF for j in xrange(N)] for i in xrange(N) ]
E = []

for _ in xrange(M):
	[a,b,c] = [ int(i) for i in raw_input().split() ]
	G[a-1][b-1] = c
	G[b-1][a-1] = c
	E.append([a-1,b-1,c])
	
for k in xrange(N):
	for i in xrange(N):
		for j in xrange(N):
			G[i][j] = min(G[i][j], G[i][k] + G[k][j])

res = 0
for [i,j,c] in E:
	res += 1 if G[i][j]	< c else 0
	
print res

Solution (Python):
from heapq import heappush, heappop
n, m = map(int, raw_input().split())
G = [[] for i in xrange(n)]
E = {}
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
    E[a-1, b-1] = E[b-1, a-1] = [c, 0]
def dijkstra(s):
    dist = [10**18]*n
    prev = [-1]*n
    que = [(0, s)]
    dist[s] = 0
    dic = set()
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for t, cost in G[v]:
            if co + cost < dist[t]:
                dist[t] = co + cost
                heappush(que, (co+cost, t))
                prev[t] = v
    for i in xrange(n):
        if prev[i] != -1:
            dic.add((i, prev[i]))
    return dic

ans = m
for i in xrange(n):
    dic = dijkstra(i)
    for k in dic:
        e = E[k]
        if e[1] == 0:
            ans -= 1
            e[1] = 1
print ans

Solution (Python):
n,m=map(int,raw_input().split())
a=[0]*m;b=[0]*m;c=[0]*m
p=[[10e9 for i in range(n)] for i in range(n)]
for i in range(n):p[i][i]=0
for i in range(m):
    a[i],b[i],c[i]=map(int,raw_input().split())
    a[i]-=1;b[i]-=1
    p[a[i]][b[i]]=p[b[i]][a[i]]=c[i]
for i in range(n):
    for j in range(n):
        for k in range(n):
            p[j][k]=min(p[j][k],p[j][i]+p[i][k])
            p[k][j]=p[j][k]
cnt=0
for i in range(m):
    if p[a[i]][b[i]]<c[i]:cnt+=1
print cnt

Solution (Python):
import heapq

def dijkstra(s,g,n):
    d=[float('inf')]*n
    d[s]=0
    pq=[]
    cnt=0
    eused=[False]*m
    visited=[False]*n
    nowe=[-1]*n
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v,c,e in g[u]:
            if d[u]+c<d[v]:
                if not visited[v]:
                    visited[v]=True
                    eused[e]=True
                    nowe[v]=e
                else:
                    idx=nowe[v]
                    eused[idx]=False
                    eused[e]=True
                    nowe[v]=e
                    
                d[v]=d[u]+c
                heapq.heappush(pq,[d[v],v])
    return eused

n,m=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
for i in xrange(m):
    a,b,c=map(int,raw_input().split())
    a-=1;b-=1;
    g[a].append([b,c,i])
    g[b].append([a,c,i])
used_edge=[False]*m
for i in xrange(n):
    tmp=dijkstra(i,g,n)
    for j in xrange(m):
        if (not used_edge[j]) and tmp[j]:
            used_edge[j]=True
ans=0
for i in xrange(m):
    if not used_edge[i]:
        ans+=1
print(ans)

Solution (Python):
n, m = [int(x) for x in raw_input().split()]

d = [[1000000000] * n for i in range(n)]

edges = []
for i in range(m):
    a, b, c = [int(x) for x in raw_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 a, b, c in edges:
    if d[a][b] < c:
        ans += 1

print ans

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

INF = 0x3f3f3f3f
dp = [[INF for i in range(110)] for j in range(110)]
v = [(0,0,0) for i in range(M)]

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

ans = 0
for i in range(M):
	if dp[v[i][0]][v[i][1]] < v[i][2]:
		ans += 1

print(ans)

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

INF = 100000000

g = [ [INF] * N for _ in range(N) ]

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

t = [ [INF] * N for _ in range(N) ]
for i in range(N):
  for j in range(N):
    t[i][j] = g[i][j]

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

ans = 0
for i in range(N):
  for j in range(i):
    if g[i][j] != INF:
      if t[i][j] != g[i][j]:
        ans += 1
print(ans)

Solution (Python):


import sys
stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()

def main():
    n,m = na()
    g = []
    for i in range(n):
        g.append([99999999]*n)
    for i in range(n):
        g[i][i] = 0
    es = []
    for i in range(m):
        a,b,c = na()
        es.append((a-1,b-1,c))
        g[a-1][b-1] = c
        g[b - 1][a - 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])
    ct = 0
    for e in es:
        if g[e[0]][e[1]] != e[2]:
            ct += 1
    print(ct)
    pass


if __name__ == '__main__':
    main()