'''
解题思路：
1、对于节点距离，建立一个字典dict_t，以字符形式存储key，距离以数字形式保存在value中，重边取最小
2、定义一个函数dis(i,j)：第i节点到第j个节点的距离，访问距离字典，有值返回，无通路返回None
3、dfs搜索，第二个参数传递走过的距离，到达终点时取最小输出，nonlocal关键字的使用
'''
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int 顶点数
# @param m int 边数
# @param graph int二维数组 一维3个数据，表示顶点到另外一个顶点的边长度是多少
# @return int
#
class Solution:
    def findShortestPath(self , n , m , graph ):
        # write code here
        
        dict_t = {}
        for ijdis in graph:
            key = str(ijdis[0])+'-'+str(ijdis[1]) 
            if key not in dict_t:
                dict_t[key] = ijdis[2]
            else:
                dict_t[key] = min(ijdis[2],dict_t[key])
        #print(dic)

        def dis(i,j):
            key = str(i)+'-'+str(j) 
            if key not in dict_t:
                return None
            else:
                return dict_t[key]
        #print(dis(1,2))
        #print(dis(2,3))
        #print(dis(3,4))

        res = 0
        minpath = float('inf')
        def search(i,res):
            nonlocal minpath
            if i==n:
                if res<minpath:
                    minpath = res
            for j in range(1,n+1):
                if dis(i,j):
                    search(j,res+dis(i,j))

        search(1,res)              
        return minpath
    
# Solution().findShortestPath(5,5,[[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]])  # 9