# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/7/19
# @File : D - Shortest Path Queries 2（二维线性DP）.py

# https://atcoder.jp/contests/abc208/tasks/abc208_d
def re(dp,N,M):
    ans = 0
    for k in range(N):
        for s in range(N):
            for t in range(N):
                dp[s][t] = min(dp[s][t],dp[s][k]+dp[k][t])
                if(dp[s][t]< 1 << 59):#代表有可达的更新（更新是指变短了）
                    ans += dp[s][t]
    return ans

if __name__ == '__main__':
    N, M = map(int, input().split())
    dp = [[1 << 60]*N for _ in range(N)]
    for _ in range(M):
        a,b,c = map(int,input().split())
        dp[a-1][b-1] = c
    for i in range(N):
        dp[i][i] = 0
    res = re(dp,N,M)
    print(res)

"""
考了一个多源最短路径和，Floyd–Warshall algorithm. Floyd-Warshall 算法用来找出每对点之间的最短距离。考研的时候的那个算法，接触过。

但是本题要求求出的是总和，k取 1-n 的每次都要加进去。

这是一道用了动态规划还需要三个循环的题目。Floyd-Warshall算法的时间复杂度是O(N3),空间复杂度O(N2)

它需要用邻接 矩阵 来储存边，这个算法通过考虑最佳子路径来得到最佳路径。

动态规划的状态转移方程，这里用（1 << 60）表示最大值INF，即不可达，如果s=t的话就是距离为0。

算法思想：每次加一个k进去，看看所有的点之间的距离是否变短，变短就更新，否则就是加了等于没加，直接等于原来的值。

所以每一次都依赖于与上一次的值的比较，dp[s][t] = min(dp[s][t],dp[s][k]+dp[k][t])。

可以原地更新dp二维数组。

"""

"""
pypy3比python3快。

关于map的知识点，返回的是一个迭代器。也可以用iter（）把数组变成迭代器，迭代器有next方法。
关于zip，zip函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表（或返回的是一个对象 迭代器 python3）

如果zip的参数是迭代器而不是数组，迭代器会实时变化到next的。

ABC = [1,2,3,4,5,6]
it = iter(ABC)
zip(ABC, ABC, ABC)：结果[(1, 1, 1), (2, 2, 2), (3, 3, 3), (4, 4, 4), (5, 5, 5), (6, 6, 6)]
zip(it, it,it)：结果[(1, 2, 3), (4, 5, 6)]


关于split，默认为所有的空字符，包括空格、换行(\n)、制表符(\t)等，经常使用的就是默认的这个。=>  input().split()
"""