#include <algorithm>
#include <climits>
#include <vector>
class Solution {
public:
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        int len = graph.size();
        vector<vector<int>> g(n,vector<int>(n,INT_MAX/2));//鄰接矩陣，標號從0開始
        for(int i=0;i<m;++i){
            g[graph[i][0]-1][graph[i][1]-1] = min(graph[i][2],g[graph[i][0]-1][graph[i][1]-1]); //去重邊
        }
        
        vector<int> dist(n,INT_MAX/2);
        vector<int> vis(n,0);
        dist[0] = 0;//0到自己的距離為0
        for(int i=0;i<n;++i){
            int x = -1;
            for(int y=0;y<n;++y){
                if(!vis[y]&&(x==-1||dist[y]<=dist[x]))
                    x = y;
            }

            vis[x] = 1;
            for(int y=0;y<n;++y){
                dist[y] = min(dist[y], dist[x]+g[x][y]);
            }
        }

        return dist[n-1];
    }
};